9084번 동전

 N개의 동전을 이용해서 M원을 만들 수 있는 가지의 수를 구하는 문제

 

M=10, N=3(2 3 5)라고 예를 들어 살펴보자.

총 10원을 2원으로 채운다면 경우의 수가 몇 개 나올까?

1	2	3	4	5	6	7	8	9	10
0	1	0	1	0	1	0	1	0	1

이렇게 될 것이다.

이제 10원을 3원으로 채워보자.

1	2	3	4	5	6	7	8	9	10
0	0	1	0	0	1	0	0	1	0

10원을 5원으로 채워보자.

1	2	3	4	5	6	7	8	9	10
0	0	0	0	1	0	0	0	0	1

총액을 dp라고 했을때 dp[5]의 경우 5원을 넣는경우만 있는게 아니라 2+3원이 나올 수 있다. 즉 경우의 수 = 2

또한 dp[7]의 경우 2+2+3, 2+5 두 가지 경우가 나올 수 있다.

 

이를 Bottom-Up 방식으로 밑에서부터 위로 채워넣어보자.

처음에 10원을 2원으로 채운다. 그리고 3원으로 채워넣을때 3원만 넣을게 아니라 2원도 같이 채워넣는다.

1	2	3	4	5	6	7	8	9	10
0	1	0->1	1	0->1	1->2	0->1	1->2	0->2	1->2

dp값은 이렇게 나올 것이다. 이때 dp[5]가 1이 나온 것을 살펴보자. dp[2]=1로 먼저 정의를 했다. 그리고 dp[5]를 구할때 dp[2+3]의 값과 같을 것이다. 즉 dp[5]=dp[2+3]=dp[2]=dp[5-3]가 나올 수 있다. 왜냐? dp[2+3]에서 3을 더한 값은 의미가 없기 때문이다. 의미가 없다는 것은 3을 더하든 빼든 경우의 수는 dp[2] 값과 같기 때문이다.

 

ex) 5원, 7원으로 22원을 만들때

5 10 15 20 -> 5원으로 만들 수 있는 수

7 14 21 -> 7원으로 만들 수 있는 수 -> 하지만 dp[12]를 구할때 dp[5+7], 결국 dp[5]의 값을 묻는 것이다. (dp[12]=1, dp[17]=dp[10+7]=1)

 

결국 dp[n]+=dp[n-동전]으로 표현할 수 있고 n은 1부터 금액까지 차례대로 구해주면 된다.(동전 1개의 값이 최소값이기 때문에 1부터 시작할 필요가 없다). 이런 식으로 채워넣는 방법을 코드화하면 이렇게 된다.