문제
자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 카지노 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 target 금액을 훔칠 수 있는 방법의 경우의 수를 계산하기 시작합니다.
예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.
$50 한 장을 훔친다
$20 두 장, $10 한 장을 훔친다
$20 한 장, $10 세 장을 훔친다
$10 다섯 장을 훔친다
훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 조지가 target 을 훔칠 수 있는 방법의 수를 리턴하세요.
입력
인자 1: target
Number 타입의 100,000 이하의 자연수
인자 2: type
Number 타입을 요소로 갖는 100 이하의 자연수를 담은 배열
출력
Number 타입을 리턴해야 합니다.
조지가 target을 훔칠 수 있는 방법의 수를 숫자로 반환합니다.
주의사항
모든 화폐는 무한하게 있다고 가정합니다.
입출력 예시
let output = ocean(50, [10, 20, 50]);
console.log(output); // 4
let output = ocean(100, [10, 20, 50]);
console.log(output); // 10
let output = ocean(30, [5, 6, 7]);
console.log(output); // 4Hint!
해당 문제는 동전 교환 알고리즘 (Coin Change)을 활용하여 풀 수 있습니다.
검색해 보시고, 연구해 보세요!
풀이방법
DP문제의 대표적인 거스름돈 구하기의 최적화 문제이다. 문제를 풀기 전에 간단한 예제를 보고 들어가는것이 더욱 도움이 될듯하다.
먼저 10원을 만들기 위한 동전 1원 2원 5원이 있다고 하자. 1원으로 10원을 만들기 위해서는 1원 10장으로 10원을 만드는 1가지 방법이 있다. 즉, 1원으로는 어떠한 금액이든 한 가지의 방법으로 밖에 만들 수 없다.
이를 표로 만들어보면,
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| 1원 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2원 | |||||||||
| 5원 | |||||||||
| total |
와 같은 방식이 되겠다. 같은 방법으로 2원으로 만들 수 있는 방법을 표로 나타내면 아래와 같이 나타나게 된다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| 1원 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2원 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 |
| 5원 | |||||||||
| total | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 |
2원으로 해당 금액을 만들때는 1원으로 만들 수 있는 모든 방법(total)로 대체 될 수 있다.
즉, 3원-2원=1원이 남는다. 2원으로 3원을 만드는 방법으로는 1원으로 1원을 만들 수 있는 방법의 수(total)를 넣으면 된다.
실제로 2원을 가지고 3원을 만드는 경우의 수는 2원+1원=3원 과 1원+1원+1원=3원의 경우의 수로 2가지가 나오게 되고 이 값이 곧 total이 되게된다.
5원의 경우도 표로 만들어보겠다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1원 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2원 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 |
| 5원 | 0 | 0 | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 4 |
| total | 1 | 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 |
이와 같이 경우의 수는 total과 같이 나오겠다. 이러한 경우의 수를 코드로 만들어보자.
코드
function ocean(target, type) {
// 거스름돈 문제는 greedy로 풀수 있디만, 이 문제는 greedy로 풀 수 없다. 왜냐면 동전의 단위가 서로 배수의 형태가 아니라 무작위로 주어진 경우이기 때문이다.
// 또한 앞서 배운 부분집합으로는 이문제를 풀 수 없는데, 동전을 각각 한 번씩 쓰는게 아니고 거스름돈이 더이상 없어질때까지 무한정으로 쓸 수 있기 때문이다.
// 이럴땐 DFS혹은 DP를 이용하면 된다.
//가장 큰 50에 대해서 1장이 들어가면 나머지 숫자에 대해서 20이 들어갔을 때와 10이 들어갔을 때의 경우를 반복한다.
let bag = new Array(target+1).fill(0)
bag[0] = 1
// target까지 0으로 채워서 배열을 만든다.
// target = 5이면, [1,0,0,0,0,0]
for(let i = 0; i < type.length; i++) {
// 훔칠 수 있는 금액들을 순회한다.
for(let j = 1; j <= target; j++){
if(type[i] <= j){ //훔칠 수 있는 화폐 종류보다 낮은 값들은 살펴볼 필요가 없기 때문에
// 훔칠 수 있는 화폐의 금액보다 크거나 같은 숫자부터 확인을 한다.
bag[j] += bag[j-type[i]];
/*
위의 target이 5일 경우를 예를 들어 살펴보자.
5월을 훔칠때 1원으로 계산을 하게 된다면,
bag[1] = bag[1] + bag[1-1]
bag[1] = 0 + 1이 된다. 즉, 1원으로 5원을 훔칠 수 있는 방법은 1가지이다.
[1,1,1,1,1,1]위에서 봤던 표의 1원 행과 동일하게 만들어지게 되는 것이다.
만약 훔칠 수 있는 종류에 2원이 있다고 한다면
3원 부분을 보면, (j = 3)일 경우
bag[3] = bag[3] + bag[3-2]
bag[3] = 2가 된다. 즉, 표에 있는 total인 갯수로 2가 되는 것이다.
bag[3] = 1 + 1로 결국 2가 되며 배열은 [1,1,2,2,1,1,]이 되겠다.
4번째 인덱스와 5번째 인덱스는 아직 값을 넣지 않았으므로 바뀌지 않았고,
결국 bag배열에는 훔칠 수 있는 화폐가 순회를 하면서 훔칠 수 있는 방법의 총 갯수가 위의 표에 total이 입력됨을 알 수 있다.
*/
}
}
}
return bag[target];
}
참조
