[백준/c++] 2294번 - 동전2

문제

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

문제

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

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

입력

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

출력

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

풀이과정

1.규칙

• dp이므로 점화식과 메모이제이션을 이용합니다.
• 동전의 가치는 100,000보다 작거나 같은 자연수입니다.
• n가지 종류의 동전을 사용해서 그 가치의 합이 k가 되도록 하되, 동전의 개수가 최소가 되도록 합니다.
• 불가능한 경우 -1을 출력합니다.

2.순서

동전1(https://it-and-life.tistory.com/144) 문제의 응용버전 입니다.

합을 구하되, 동전의 갯수가 최소여야 합니다.

가치(k)는 4, 동전의 종류(n)는 1,2,3인 경우를 메모이제이션으로 생각해보면

	coin[1]=1	coin[2]=2	coin[3]=3	최소 개수
1	1 (1개)	0	0	1개, dp[1]=1
2	1+1 (2개)	2 (1개)	0	1개, dp[2]=1
3	1+1+1 (3개)	2+1 (2개)	3 (1개)	1개, dp[3]=1
4	1+1+1+1 (4개)	2+2 (2개)	3+1 (2개)	2개, dp[4]=2

로, 정답이 2가 됩니다.

dp[0]=0으로, 나머지는 최대가치인 100001로 초기화 해준 뒤,

빨간색행을 i로, 보라색열을 j로 생각해보면  j - i 가 0 이상일경우, dp[j]와 dp[j-coin[i]]+1중 작은 값이 dp[j]에 쓰여짐을 알 수있습니다.

예를들어,

j : 1, i : 1일 경우, dp[1]은 100001, dp[1-coin[1]]+1은 dp[0]+1=1이므로 dp[1]=1

j : 2, i : 1일 경우, dp[2]은 100001, dp[2-coin[1]]+1은 dp[1]+1=2이므로, dp[2]=2,

j : 3, i : 1일 경우, dp[3]은 100001, dp[3-coin[1]]+1은 dp[2]+1=3이므로 dp[3]=3,

j : 3, i : 2일 경우, dp[3]은 3, dp[3-coin[2]]+1은 dp[1]+1=2 이므로 dp[3]=2,

j : 3, i : 3일 경우, dp[3]은 2, dp[3-coin[3]]+1은 dp[0]+1=1 이므로 dp[3]=1

의 순서로 진행되며 정답이 나오게 됩니다.

따라서 점화식은 (i : 1~n) , (j : coin[i]~k) 일때 dp[j] = min(dp[j], dp[j-coin[i]]+1) 이 됩니다.

3.코드

* dp[k]가 불가능한 경우인지도 꼭 체크해 줘야 합니다. *