[JS] 코딩 테스트 문제 : 동전교환 [DFS]

문제 : 동전교환

문제 설명

다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

▣ 입력설명

첫 번째 줄에는 동전의 종류 개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다. 각 동전의 종류는 100원을 넘지 않는다.

▣ 출력설명

첫 번째 줄에 거슬러 줄 동전의 최소 개수를 출력한다.

▣ 입력예제 1

3
1 2 5
15

▣ 출력예제 1

3
설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

내코드

function solution(m, arr) {
  let sortArr = arr.sort((a, b) => b - a); // 동전을 내림차순으로 정리
  // 주어진 거스름돈을 가장 큰 동전으로 나눈 몫을 올림한 값으로 거스름돈에 사용될 가능한 최소 개수를 의미
  const MIN_POSSIE_COUNT = Math.ceil(m / arr[0]);
  let answer = Number.MIN_SAFE_INTEGER;
  let answerArr = []; // 로직과 별개로 정답을 구하는데 사용된 동전조합을 의미할 배열

  // 남은 거스름돈을 의미할 인자 num, 계산한 사용한 동전 개수를 의미할 인자 count, 현재까지 사용된 동전 조합을 의미할 배열 인자 checkArr
  // 위 인자들로 남은 거스름돈을 재귀적으로 계산할 DFS 함수 선언
  function DFS(num, count = 0, checkArr = []) {
    // 이미 가능한 최소 값에 도달했다면 이후 함수과정을 스킵
    if (answer === MAX_POSSIE_COUNT) return;

    // 거스름돈이 0 일 때 현재까지 사용한 동전 개수를 현재까지 최소값과 비교 후 더 작은 경우 저장
    if (num === 0) {
      answer = Math.min(answer, count);
      answerArr = checkArr;
      return;
    }

    // 거스름돈이 0 보다작아진 즉 제대로 거스름돈을 줄 수 없는 경우이거나
    // 이미 거스름돈에 사용한 동전이 최소값과 같거나 크다면 남은 거스름돈 계산이 의미없으므로 함수 종료
    if (num < 0 || count >= answer) return;
    // 아직 거스름돈이 남은 경우 높은 동전 부터 계산한 거스름돈을 인자로 DFS 함수에 재귀적으로 호출
    else {
      for (let i = 0; i < sortArr.length; i++)
        DFS(num - sortArr[i], count + 1, [...checkArr, sortArr[i]]);
    }
  }

  DFS(m);
  console.log("거스름돈에 사용한 동전 조합: ", answerArr);
  return answer;
}

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

풀이

1. 주어진 여러 단위의 동전들 (arr 배열) 을 내림차순으로 정렬, 주어진 거스름돈을 가장 큰 동전(arr[0]) 으로 나눈 몫을 올림한 값으로 거스름돈에 사용될 가능한 최소 동전 개수를 의미
2. 남은 거스름돈을 의미할 인자 num, 계산한 사용한 동전 개수를 의미할 인자 count 위 인자들로 남은 거스름돈을 재귀적으로 계산할 DFS 함수 선언
3. 거스름돈을 높은 동전부터 계산한 거스름돈을 인자로 DFS 함수를 재귀적으로 호출
4. 계산해 가면서 거스름돈이 0 일 때 모든 거스름 계산 과정이 마무리된 것으로 현재까지 사용한 동전 개수를 현재까지 최소 값(answer)과 비교 후 더 작은 경우 정답 변수(answer) 에 저장
5. 거스름돈 계산 과정에서 거스름돈이 0 보다 작아진 즉 제대로 거스름돈을 줄 수 없는 경우이거나, 이미 거스름돈에 사용한 동전이 최소 값과 같거나 크다면 남은 거스름돈 계산이 의미 없으므로 함수 종료해 이후 거스름 계산 과정을 스킵
6. 현재까지 최소 값(answer)이 이미 가능한 최소 값(MIN_POSSIE_COUNT)에 도달했다면 더 이상 최소 값을 구할 필요가 없으므로 return 하여 이후 모든 재귀 함수 과정을 스킵

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/unit/64103