https://leetcode.com/problems/coin-change/description/
이 문제를 코인 크기대로 정렬한 뒤 큰 순서대로 나누고 나머지 연산으로 누적해간다는 아이디어를 떠올린다면 틀린 것이다. 모르겠으면 아래 경우를 테스트케이스에 추가해 보라.
coins = [3, 5], amount = 9
아이디어는 아래와 같다.
우선 amount에 해당하는 가장 적은 코인 소비 수를 저장하기 위해 dp 배열을 만드는데,
0부터 amount까지 담아야 하므로 크기는 amount + 1로 설정한다.
초기값은 -1이나 Integer.MAX_VALUE와 같이 확실히 플래그를 구분할 수 있는 것이면 좋다.
코인 배열을 순회하면서 해당 코인으로 접근할 수 있는 index의 값을 세팅한다.
for (int coin : coins)
해당 코인으로 접근할 수 있는 최대 범위는 아래와 같다.
for (int i=coin; i<=amount; i++)
다만 해당 코인으로 접근 가능한 부분만 갱신해야 하기 때문에 아래와 같은 조건이 붙는다. (dp배열 초기화를 Integer.MAX_VALUE로 초기화한 경우)
if (dp[i - coin] != Integer.MAX_VALUE)
i는 최대범위 탐색을 위해 1씩 증가되는 값이므로 "i - coin"으로 접근한 값이 초기값이 아니라는 이야기는 0 혹은 해당 코인으로 나눠질 수 있는 값임을 의미한다.
이 때 Math.min을 사용해서 원래 들어있던 값과 현재 코인을 하나 더 썼을 때의 값 중 낮은 값으로 세팅한다.
시간복잡도는 O(n⋅m)이다.
class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int coin : coins) {
for (int i=coin; i<=amount; i++) {
if (dp[i - coin] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}