[백준/DP] 2293번 동전1 (골드5, python)

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

2293번: 동전 1

아이디어

DP 문제이다.

동전이 추가될 때 마다 추가된 경우의 수를 더해주면서 구한다.

 

dp[0]을 1로 먼저 초기화하는 이유는 동전 본인의 인덱스의 경우 1을 더해줘야 하는데 (if j in coins) 이 부분을 없애고 점화식을 그대로 사용하기 위해서이다. (j-i가 0이 되므로 dp[0]인 1이 추가된다.)

 

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

 

동전을 "1" 만 사용할 때는 각각의 수를 1, 1+1, 1+1+1, 1+1+....+1 이 경우로 만들 수 있다.

 

사용할 수 있는 동전에 2가 추가되면,(두번째 라인)

2를 만들수 있는 경우의 수가 1가지 추가된다. (2 동전 하나로 만들기)

3을 만들 수 있는 경우는, 1(3-2)을 만드는 경우의 수에 각각 2를 더한 경우이다. 

dp[1]은 1 이므로 마찬가지로 1가지가 추가된다. 

4를 만들 수 있는 경우의 수는 2(4-2)를 만들 수 있는 경우의 수에 각각 2를 더한 경우이기 때문에 2를 만드는 경우의 수를 더해주면 된다.

..

즉, dp[j] += dp[j-i] 라는 점화식이 나오게 된다.

 

말이 조금 어려울 수 있는데, 동전 "2"를 추가했을 때 dp[4]의 경우를 생각해보면,

4에서 2를 뺀 2를 만들 수 있는 모든 경우의 수는 1+1과 2 로 총 2개이다.

4는 2를 만드는 모든 경우에 동전 2를 추가하면 되기 때문에 마찬가지로 2가지 경우가 생기게 된다.

 

2를 만드는 경우 + 동전 2 = 4를 만드는 경우

1+1 + 2 = 4

2 + 2 = 4

-> 경우의 수는 변하지 않음

 

전체코드

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
coins.sort()
dp = [0] * (k + 1)
dp[0] = 1

for i in coins:
    for j in range(i, k + 1):
        dp[j] += dp[j-i]


print(dp[k])

 

번외

친구에게 설명해주기..ㅎㅎ