Problem
n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
Solution 1
문제 접근 순서
동전 1과는 다르게 배수로 접근할 수 없었던 문제였다. 숫자들은 임의로 주어지고, 어떻게든 최소의 횟수로 구하는 문제인데 DP가 가장 적합하다 생각했다.
각설하고, 풀이방법은 다음과 같다.
처음 DP배열을 생성하는데 최솟값을 구하기 위한 DP이므로 문제 조건에서 벗어나는 값을 초기화한다.
비교를 하며 DP의 값을 최솟값으로 갱신해주는데 두가지 조건을 비교하며 갱신한다.
- DP[j+1]의 값을 그대로 가져가는 경우
- DP[j-coin[i]]가 최솟값을 가져가는 경우
두 가지 비교조건을 사용하여 DP[j+1]을 계속 구해나아가고 마지막 인덱스인 DP[K]에서 최솟값을 구하면된다. 그래서 DP는 K+1로 설정을 해주어야한다. 하지만 항상 그렇게 하기 귀찮으니까 항상 문제조건보다 +1하는것이 편하다. 그러면 인덱스가 null pointer를 가리키지도 않는다.
예제 입력
coin이 1일때,
| DP1 | INF | INF | INF | INF | INF | INF | INF | ... | INF | INF | INF | | :-----: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | DP2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ... | 13 | 14 | 15 |
DP[0]은 무조건 0으로 해주어야한다. 그렇지 않으면 처음 최솟값을 구하지 못한다.
DP[0]과 DP[1 - 1] + 1 과비교하게 된다. 만약 여기서 DP[1-1]이 INF이면 최솟값을 못하기 때문에 반드시 0으로 초기화시켜줘야한다.
coin이 5일때,
| DP1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ... | 13 | 14 | 15 |
| :-----: | :-: | :-: | :-: | :-: | :-: | :-----: | :-: | :-: | :-: | :-: | :-: |
| DP2 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | ... | 1 | 2 | 3 |
DP[1]부터 스캔하는것이 아닌 coin[i]부터 시작하게 된다. coin이 5니까 DP[5]부터 시작하게 되는데, DP[5-5]+1 은 2이므로 위에 6보다 더 작다. 그러므로 최솟값을 갱신하게 된다.
이러한 방식으로 계속해서 coin을 기준으로 계속해서 최솟값을 갱신하게 된다.
Source 1
for (int i = 1; i <= N; i++) { for (int j = coin[i]; j <= K; j++) { dp[j + 1] = min(dp[j + 1], dp[j - coin[i]] + 1); } }
답지를 보고 힌트를 얻은 문제였다. 드릅게 어렵다.