👉 문제
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.
You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
입출력 예시:
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.✨ 풀이
class Solution {
public int change(int amount, int[] coins) {
int[] arr = new int[amount+1];
Arrays.fill(arr, 0);
arr[0] =1;
for( int c : coins) {
for(int j = c; j <= amount; j++) {
arr[j] += arr[j-c];
}
} return arr[amount];
}
}풀이 노트:
-
가장 적은 양의 동전으로 잔돈을 돌려주는 그리디 알고리즘은 푼 적이 있는데, 이 문제의 경우 접근을 떠올리기 어려웠다. 나머지가 0인 경우와 아닌 경우로 나누어 후자의 경우 amount에서 큰 동전부터 차감하는 식으로 풀면 어떨까 생각했는데, 막상 구현하려니 필요한 만큼 동전을 쓰고 더 적은 동전으로 옮겨가는 것이 구현하기 어려웠다.
그래서 이번 문제의 경우 다른 사람들의 풀이를 많이 보고 공부했다. 그중 효율이 좋고 새로운 공부가 된 방식인 다이나믹 프로그래밍 풀이를 가져왔다. (다이나믹 프로그래밍: 문제를 더 작은 문제로 나누고, 작은 문제들의 값을 활용해 궁극적인 정답을 도출해내는 방식) -
amount라는 최종값에 필요한 동전의 수를 바로 구하는 것이 아니라,0,1,2,...,amount이런 식으로 가장 적은 값부터 시작해 필요한 동전의 수를 구해 앞전의 값에다 새로운 방식을 더하는 방식이다.
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1입출력 예시를 빌려오자면,
5를 만드는 경우의 수를 구하기 앞서 0부터 4까지 구해볼 수 있다.
아무 동전이 없을 때는 0을 제외하고는 만들 방법이 없기 때문에 방법의 수가 0이다. 0일 때는 아무 동전이 필요 없으니 1이다.
1이라는 동전으로 0부터 5까지의 값을 만드는 건 아예 내지 않거나, 전부 1로만 구성되게 만드는 것밖에 없으니 방법의 수가 전부 1이다.
2라는 동전이 새로 추가되었다. 만들어야 하는 값이 2가 되기 전까지는 새로운 동전인 2를 쓸 필요가 없으니 위에서 구한 방법의 수인 1을 그대로 가져와서 넣는다.
만들 값이 2가 됐을 때, 방법의 1+1, 2 2가지가 있다. 사람인 우리는 이 점을 직관적으로 떠올릴 수 있다.
그러나 컴퓨터는 그렇지 않기 때문에 다이나믹 프로그래밍의 방식으로 생각해봐야 한다.
우선 우리는 동전 1로 값 2를 만드는 방법은 한 가지라는 것을 구해놓았다. 더 구해야 할 방법은 새로운 동전인 2를 추가한 경우이다.
그럼 2에서 2를 빼보면 된다. 2에서 2를 빼면 0이다. 앞서 말했듯 0은 요구하는 동전이 없기 때문에 어떤 동전을 들고 있어도 다 디폴트로 1가지 방법을 가지고 있다고 볼 수 있다. 바로 내지 않는 것이다.
그럼 2를 만드는 방법은 1을 만드는 방법과, 2에서 새로운 동전인 2를 뺐을 경우 필요한 방법 두 가지를 합치면 구할 수 있는 것이다. 고로 1+1=2가 된다. 
이런 방식으로 최종 값인 5까지 풀이를 진행한다.
0부터 4까지는 새로운 동전인 5를 쓸 수 없기 때문에 윗 행에서 구한 수를 그대로 내려받는다.
5가 되었을 때, 새로운 동전인 5를 사용할 수 있게 되었기 때문에 기존에 구한 방법의 수인 3에 5-5=0열에 구해둔 방법의 수인 1을 더해서 4라는 방법의 수를 구할 수 있다.
class Solution {
public int change(int amount, int[] coins) {
int[] arr = new int[amount+1];
Arrays.fill(arr, 0);
arr[0] =1;
for( int c : coins) {
for(int j = c; j <= amount; j++) {
arr[j] += arr[j-c];
}
} return arr[amount];
}
}이런 풀이 과정을 녹여낸 것이 이 코드다. 0부터 amount까지의 자리만큼 긴 배열 arr을 만들어 디폴트값인 1을 첫 칸에 담는다. 구해야 하는 값의 자리에 이전에 계산한 방법의 수를 더해주며 동전 배열을 순회한다.
이 풀이는 릿코드에 제출하여 통과된 코드들 중 효율성이 상당히 좋은 편에 속한다. 시간 복잡도는 O(NM)이다. (N = coins 길이, M = amount 크기)
