Question
다양한 동전들을 가지고 특정 금액을 만들 수 있는 모든 경우의 수를 리턴해야 합니다.
•
예를 들어, 100원, 500원짜리 동전을 가지고 1,000원을 만들 수 있는 방법은 총 3가지 입니다.
•
100원 10개, 100원 5개 + 500원 1개, 500원 2개
입력
인자 1 : total
•
number 타입의 이하의 자연수
인자 2 : coins
•
number 타입을 요소로 갖는 배열
•
coins.length는 10,000 이하
•
coins[i]는 20 이하의 양의 정수
출력
•
number 타입을 리턴해야 합니다.
주의사항
•
동전의 금액은 다양하게 주어집니다.
•
coins는 오름차순으로 정렬되어 있습니다.
•
각 동전의 개수는 무수히 많다고 가정합니다.
Test Case 1
let total = 10;
let coins = [1, 5];
let output = coinChange(total, coins);
console.log(output); // --> 3
Shell
복사
Test Case 2
total = 4;
coins = [1, 2, 3];
output = coinChange(total, coins);
console.log(output); // --> 4 ([1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3])
Shell
복사
Solve
DP
const coinChange = function (total, coins) {
const cases = [1];
for(let i = 1; i <= total; i++) {
cases[i] = 0;
}
for (let i = 0; i < coins.length; i++) {
for (let j = 1; j <= total; j++) {
if (coins[i] <= j) cases[j] += cases[j - coins[i]];
}
}
return cases[total];
};
JavaScript
복사
실행시간 : ms