인프런 커뮤니티 질문&답변

function solution(coins, m) {
  coins.sort((a, b) => b - a);
  let ans = 0;

  function DFS(L, sum) {

    if (sum > m) {
      return;
    }
    if (sum === m) {
      ans = L;

      return "end";
    } else {
      for (let i = 0; i < coins.length; i++) {
        if (DFS(L + 1, sum + coins[i]) === "end") return "end";
      }
    }
  }
  DFS(0, 0);
  return ans;
}

동전 교환 문제에서 강사님께서 가르쳐주신 코드도 실습해 본 후, 제 나름대로 작성해본 코드입니다.

제 얕은 생각으로는 위 코드처럼 가장 먼저 동전 종류를 내림차순으로 정렬한 후, DFS를 가지쳐 내려나간다면, 가장 큰 단위부터 적용해나가므로 맨 처음 종료조건에 도달해 ans에 대입되는 값이 무조건 최소동전 개수가 되지 않을까 생각해서 이렇게 작성했습니다.

이 풀이가 틀린지 궁금하고, 만일 맞다면 시간복잡도 상 효율이 극단적으로 떨어지는 최악의 경우가 존재할 지 또한 궁금합니다.

귀한 시간 내어 읽어주셔서 감사합니다.