[코테강의/JS] 동전교환

동전교환
다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환
해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.
▣ 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종
류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다.
▣ 출력설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.
▣ 입력예제 1
3
1 2 5
15
▣ 출력예제 1
3
설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

이 문제를 풀면서 깨달은 점이 있는데

우선 강사님이 개념을 알려주고 그에 맞는 문제를 풀어주시고 있다는점. 내 능지..

전 시간에 배운 개념이 중복순열이므로 이번문제는 중복순열문제일텐데, 왜 그런지에 대해 고민을 해보았다.

조금 다른 느낌이지만 거슬러줄 금액이 정해져 있고 동전 하나를 계속 뽑을 수 있다.

15 를 만들어주기위해 1원짜리 동전을 15개를 뽑아야 된다는 것처럼말이다.

뽑는다는게 중복조합과 뭔가 혼동이 있는 것 같다.

하지만 이게 중복조합이 아닌 이유는 Array에 index에 동전의 cost가 정해져있다는 것이다.

1원짜리 동전 15개를 거슬러주고나면 재귀를 빠져나오는데 이제 백트래킹이 되어 1원 14개 2원 1개 의 조건이 되기 때문이다.

 

문제풀이

나는 처음에 로직을 짤때 S>= limit 일때 다시 if문으로 같은경우를 분기처리 해주었는데

const dfs = (L, S) => {
  if (S >= limit) {
    if (S === limit) {
      minn = Math.min(minn, L);
    }
    return
  } else {
    for (let i = 0; i < coinNumber; i++) {
      dfs(L + 1, S + cointKind[i]);
    }
  }
};

 

다음처럼 최상위에서 limit 보다 큰 경우 return 하는게 더 깔끔한 것 같다.

const dfs = (L, S) => {
  if (S > limit) return;
  if (S === limit) {
    minn = Math.min(minn, L);
  } else {
    for (let i = 0; i < coinNumber; i++) {
      dfs(L + 1, S + cointKind[i]);
    }
  }
};

 

더 나아가서 최적화를 시킨 모습이다.

이미 deps 3 에서 답을 가지고 있다면 이후 백트레킹되어 다시 뻗어질때 deps 4 이상은 찾을 필요가 없기 때문이다. 

const dfs = (L, S) => {
  if (S > limit) return;
  if (L >= answer) return;
  if (S === limit) {
    minn = Math.min(minn, L);
  } else {
    for (let i = 0; i < coinNumber; i++) {
      dfs(L + 1, S + cointKind[i]);
    }
  }
};

 

전체코드

// 완전탐색으로 풀어야할까

// 아 이게 중복순열이구나
// 3
// 1 2 5
// 동전을 중복해서 뽑는다는 것이니까
// 지렸다
// 그러면 아까 배웠던 로직을 응용하면 될것같은데

const fs = require("fs");

BOJkey = 1;

let input = fs
  .readFileSync(BOJkey ? "./코딩테스트강의/섹션8/input.txt" : "./dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map((v) => +v));

console.log(input);
let coinNumber = input[0][0];
let cointKind = input[1];
let limit = input[2][0];
let minn = Number.MAX_SAFE_INTEGER;
const dfs = (L, S) => {
  if (S > limit) return;
  if (S === limit) {
    minn = Math.min(minn, L);
  } else {
    for (let i = 0; i < coinNumber; i++) {
      dfs(L + 1, S + cointKind[i]);
    }
  }
};

dfs(0, 0);
console.log(minn);