DFS - 동전 교환

동전교환

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

각 단위의 동전은 무한정 쓸 수 있다.

 

▣ 입력설명

첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다.

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

각 동전의 종류는 100원을 넘지 않는다.

 

▣ 출력설명

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

 

▣ 입력예제 1

3

1 2 5

15

 

▣ 출력예제 1

3

---

동전을 무한정 사용할 수 있다는 조건이 있다.

예제를 기반으로 1을 15개 사용할 수 있고, 1을 13개, 2를 1개 사용할 수도 있다. 5를 3개 사용할 수도 있다.

중복순열과 유사한 문제이다.

풀이과정을 그림으로 표현했는데 해석하자면 다음과 같다.

재귀함수를 D라고 정의한다면, D는 L과 sum이라는 파라미터를 받는다. 이때 L은 동전의 갯수에 해당하고, sum은 지금까지 받은 동전의 누적합이다.

재귀함수를 호출할 때마다 동전의 갯수만큼 반복문을 돌린다. 그리고 동전의 누적합이 거스름돈과 일치하다면 L에 해당하는 동전의 갯수들의 최솟값이 바로 문제의 답이다.

 

let input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
let n = Number(input[0]);
let money = input[1].split(' ').map(Number);
let m = Number(input[2]);
let ret = Number.MAX_SAFE_INTEGER;

function solve(l, sum) {
  if (sum > m) return;
  if (sum === m) {
    ret = Math.min(ret, l);
    return;
  } else {
    for (let i = 0; i < money.length; i++) {
      solve(l + 1, sum + money[i]);
    }
  }
}

function solution() {
  solve(0, 0);
  return ret;
}

console.log(solution());

코드로 표현하면 다음과 같다.

여기서 기저조건이 중요 포인트이다. sum이 m보다 클 때는 함수를 종료하라는 조건이 없다면 sum이 m보다 큰 순간에 재귀함수가 종료되지 않고 콜스택이 터진다. 따라서 다음과 같은 기저조건을 반드시 추가해야한다.

 

이 코드도 돌아가긴 하지만 너무 불필요한 연산들이 많이 들어가 있다. 

현재 구한 최솟값보다 동전의 갯수가 크거나 같다면 함수를 종료해야 연산을 줄일 수 있다.

ret가 3일때, 3보다 작은 1이나 2인 경우를 찾아야지 3과 같거나 큰 것들은 살펴볼 필요가 없다는 것이다.

let input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
let n = Number(input[0]);
let money = input[1].split(' ').map(Number);
let m = Number(input[2]);
let ret = Number.MAX_SAFE_INTEGER;

function solve(l, sum) {
  if (sum > m) return;
  if (ret <= l) return;
  if (sum === m) {
    ret = Math.min(ret, l);
    return;
  } else {
    for (let i = 0; i < money.length; i++) {
      solve(l + 1, sum + money[i]);
    }
  }
}

function solution() {
  solve(0, 0);
  return ret;
}

console.log(solution());

엣지 케이스를 제거하니 다른 입력값으로 테스트했을 때 훨씬 빠른 속도로 연산이 되었다.

불필요한 연산을 줄이는 코드의 중요성을 깨달았다.

 

DFS는 조건에 맞는 것을 찾아서 밑으로 가지를 치며 내려가는 구조이다.

이 구조를 적용할 수 있다면 재귀를 활용한 DFS 구현이 가능하다.

왜 재귀를 활용해야하고 DFS로 문제를 풀어야하는지 항상 상기시키면서 공부하자.

이유없이 그냥 사용해야 문제가 풀리니까 이런 생각은 알고리즘을 너무 재미없게 만든다.