동전 교환 : DFS (Cut Edge Tech)

내 풀이

function solution(m, arr) {
  let answer = Number.MAX_SAFE_INTEGER;
  function DFS(k, sum) {
    if (sum > m) return;
    else if (sum === m) {
      answer = Math.min(answer, k);
      return;
    }
    for (let x of arr) {
      DFS(k + 1, sum + x);
    }
  }
  DFS(0, 0);
  return answer;
}

let arr = [1, 2, 5];
console.log(solution(15, arr));

Solution 풀이와 비교해보면, 중간에 k가 answer(이미 min값)보다 초과한 경우 미리 컷 해주었으면 좀 더 효율적이였을 것 같다.

Solution 풀이

function solution(m, arr) {
  let answer = Number.MAX_SAFE_INTEGER;
  let n = arr.length;
  function DFS(L, sum) {
    if (sum > m) return;
    if (L >= answer) return;
    if (sum === m) {
      answer = Math.min(answer, L);
    } else {
      for (let i = 0; i < n; i++) {
        DFS(L + 1, sum + arr[i]);
      }
    }
  }
  DFS(0, 0);
  return answer;
}

let arr = [1, 2, 5];
console.log(solution(15, arr));

if (L >= answer) 부분만 내 풀이에 넣어주었으면 훨씬 좋았을 것 같다!