[인프런 섹션8] 동전교환 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션8] 동전교환 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-29

1. 가장 적은 수의 동전으로 교환

• DP인지 그리디인지 헷갈림

2. DFS 종료조건

• 중복순열로 구현 (for 반복문)
• 거스름돈이 target보다 크거나 같으면 종료 --> Math.min()을 써야하나?
• 거스름돈이 target과 같은 경우, 동전을 뽑은 횟수인 v를 출력

if (sum >= target) {
  if (sum === target) console.log(v);
  return;
}

3. DFS 로직

• 중복가능이므로, v는 뽑은 숫자가 아니라 뽑은 횟수
• for 반복문 사용

for (let i=0; i<arr.length; i++) {
  sum += arr[i];
  DFS(v+1);
  sum -= arr[i];
}

4. v의 초기값

• 동전을 추가하고 나서 v+1
• 초기값은 0

✍️소스코드

2021-06-29

let arr = [1, 2, 5];
let target = 15;
let sum = 0;
let min = Number.MAX_SAFE_INTEGER;

function DFS(v) {
  if (sum >= target) {
    if (sum === target) min = Math.min(min, v);
    return;
  }

  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
    DFS(v + 1);
    sum -= arr[i];
  }
}

DFS(0);
console.log(min);