[Python] 백준 2294번 - 동전 2 (골드 5)

https://www.acmicpc.net/problem/2294

2294번: 동전 2

 

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 다이나믹 프로그래밍

 

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

 

---

난 멍청이다.

골드 5 문제도 못 푸는 멍청이다.

 

딱 봐도 DP문제에 비슷한 문제 푼 적 있는 거 같은데 못 풀었다.

 

우선 반례들 모음이다.

 

3 15
1
5
12
정답: 3

1 2
3
정답: -1

18 52
25
15 
17 
14
8 
30 
27 
11 
20 
6 
13 
13 
8 
9 
19 
15 
29 
30
정답: 2

8 17
13
1 
10 
11 
1 
8
14 
12
정답: 3

---

처음에 어찌 저지 풀었다.

IndexError가 발생하는 것이다.

난 어디서 IndexError가 발생하나 궁금했는데

 

두 번째 반례인

1 2
3
정답: -1

위를 보면

k=2로 dp 배열이 0, 1, 2까지 생성되지 않을 것이다.

 

근데 난 처음에 dp[coin[i]] = 1을 선언하다 보니 dp[3] -> IndexError 발생하게 된 것이다.

 

---

두 번째로는 동전 조합이 만들어질 수 없는데 무지성으로 +1을 하다 보니 생긴 오답이었다.

 

3 7
3   
4
6
정답: 2

만약 위 반례에서 5원을 만드는 조합은? 0개이다.

하지만 처음에 내가 푼 코드에서는 dp[i] = dp[i - coin[j]] + 1을 그냥 계속해주다 보니

dp[i] = 1이 되어버린 것이다.

 

dp[5] = dp[5 - 3] + 1
dp[5] = dp[2] + 1
dp[5] = 0 + 1
dp[5] = 1

위의 방법으로 조합이 없는 코인 방식에서도 1이 계속해서 들어가면서 오답이 되었다.

 

위의 두 가지 문제점을 수정하고 나서야 정답이 출력되었다.

 

나는 멍청이다.