[python] 백준 2293번: 동전1(DP)

# 2293 동전1
https://www.acmicpc.net/problem/2293

2293번: 동전 1

⭐ 코드

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
coins = []
for _ in range(n):
    coins.append(int(input()))

dp = [0] * (k + 1)
dp[0] = 1

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

print(dp[-1])

📝 풀이

dp문제는 접근방법 자체를 도출해내는게 어려운 것 같다. n개의 동전 종류가 주어지고 동전을 사용해서 k원이 되는 경우의 수를 구하면 된다. 동전의 구성만 다르다면 몇개를 써도 상관없다는 조건이 있다.

먼저 dp리스트에 대해서 짚고 넘어가자면, dp리스트는 목표 금액인 10원의 크기 +1만큼 만들어주면 되고 목표 금액을 만드는 경우의 수는 dp리스트 마지막에 기록되게 된다.

테스트케이스에서 처럼 만약 1,2,5의 동전 구성이 주어진다면 이를 가지고 10원을 만드는 경우는 다음과 같다.
구성만 다르다면 몇개를 사용해도 상관없다고 했으니 1원, 2원, 5원으로 10원을 만드는 방법을 생각해보자.

1원
1+1+1+1+1 ~ +1
1원으로 10을 만드는 방법은 1가지이다.

2원
이 방법에서 2원이 추가되게 되면 이전에 1원이 만들 수 있는 방법에 추가적으로 경우의 수를 더해주면 된다.

5원
5원도 마찬가지로 1과 2로 만들 수 있는 경우에 수에 5를 섞어서 만들 수 있는 경우의 수를 더해주면 된다.

이를 표로 만들면 다음과 같다.

	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]	dp[9]	dp[10]
1원	1	1	1+1	1+1+1	1+1+1+1	1+1+1+1+1	1+1+ ~1	1+1~1	1+~1	1+~1	1+~1
2원	1		1+1 2	1+1+1 1+2	1+1+1 1+1+2 2+2	1+1+1+1+1 1+1+1+2 1+2+2	1+1+~1 1+1+1+1+2 1+1+2+2 2+2+2				1+~1 1+1+1+1+1+1+1+2 ... 2+2+2+2+2
5원	1					1+1+1+1+1 1+1+1+2 1+2+2 5	1+1+~1 1+1+1+1+2 1+1+2+2 2+2+2 1+5				1+~1 1+1+1+1+1+1+1+2 ... 2+2+2+2+2 1+1+1+1+5 1+1+1+2+5 1+2+2+5 5+5

일일이 하나씩 적기가 너무 힘들어서 중간이 빵꾸가 났는데 결국 핵심은 dp[10], 즉 10원을 만들기 위한 경우의 수는 1원과 2원을 사용했을때의 경우에수에 5원으로 10원을 만드는 경우의 수를 더해주면 된다.(빨간색으로 표시된 부분이 추가된 경우의 수) 동전의 구성이 추가될 때마다 이전에 구했던 경우에 수에서 추가된 동전으로 10원을 만드는 경우의 수를 더해주면 된다.

🔓 정답 코드 뜯어보기

dp = [0] * (k + 1) # 1번
dp[0] = 1 # 

for i in coins: # # 2번
    for j in range(i, k+1): # 3번
        if j - i >= 0: # 4번
            dp[j] += dp[j-i] # 5번

print(dp[-1]) # 6번

# 1번
합이 k원이 되는 경우의 수를 구하기 위해 dp에 0 * (k+1)을 만들어준다. dp[1]은 1원이 되는 경우의 수 dp[2]는 2원이 되는 경우의 수를 기록하는 것이고 dp[k]는 k원이 되는 경우의 수이다.

# 2번
for문에서 코인 구성들을 순회한다.

# 3번
dp를 순회하면서 특정 가치를 가진 동전을 썼을 때 합이 j원이 되는 경우의 수가 있다면 dp리스트에 기록한다.

# 4번
코인의 종류(1,2,5)보다 만들어야하는 값(k)가 더 커야하므로 j-i 조건문을 걸어준다. 만약 해당 조건을 통과한다면 dp리스트에 기록시켜준다.

# 5번
현재 dp[j]에 이전에 만들었던 경우의 수들을 더해준다.

# 6번
dp마지막에 기록된 값이 k원이 되는 경우의 수 이므로 dp[-1]을 출력시켜준다.