백준 2293 - 동전 1 (파이썬)

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

 

풀이

dp[i][j] → i번까지의 동전을 사용하여 j원을 만드는 경우의 수

점화식

1. 동전 i를 사용하지 않는 경우
   1. dp[i][j] = dp[i - 1][j]
2. 동전 i를 사용하는 경우
   1. dp[i][j] += dp[i][j - V[i]]
   2. 현재 동전을 사용하면 j - V[i]를 만드는 방법에서 해당 동전을 추가한 방법이 가능

초기에 코드는 다음과 같다.

# 백준 2293 - 동전 1
# 분류 : 다이나믹 프로그래밍

N, K = map(int, input().split())
V = [0] * N

for i in range(N) :
    V[i] = int(input())

# (i, j) : i번 까지의 동전을 사용해서 j원을 만드는 경우의 수
dp = [[0] * (K + 1) for i in range(N)]

# dp[0][~]
for i in range(K + 1) :
    if i % V[0] == 0 :
        dp[0][i] = 1

for i in range(1, N) :
    for j in range(K + 1) :
        dp[i][j] = dp[i - 1][j]
        if j >= V[i] :
            dp[i][j] += dp[i][j - V[i]]
            
print(dp[N - 1][K])

기존의 2차원 DP테이블을 사용하면 문제에서 주어진 메모리 사용량인 4MB를 초과하게 된다. 따라서 1차원 리스트(prev, curr)을 사용해서 최적화 한다.

1. prev[j] → 이전 동전까지 사용하여 j원을 만드는 방법의 수
2. curr[j] → 현재 동전까지 사용하여 j원을 만드는 방법의 수

또한 점화식을 1차원으로 변형한다.

curr[j] = prev[j]
if j >= V[i]:
    curr[j] += curr[j - V[i]]

1. 기존 dp[i - 1][j]는 prev[j]로 대체
2. dp[i][j - V[i]]는 curr[j - V[i]]로 대체

prev = curr

현재 동전(curr)을 업데이트한 후, prev에 저장하여 다음 반복에 사용

코드

# 백준 2293 - 동전 1
# 분류 : 다이나믹 프로그래밍

N, K = map(int, input().split())
V = [0] * N

for i in range(N) :
    V[i] = int(input())

prev = [0] * (K + 1)
curr = [0] * (K + 1)

for i in range(K + 1) :
    if i % V[0] == 0 :
        prev[i] = 1

for i in range(1, N) :
    for j in range(K + 1) :
        curr[j] = prev[j]
        if j >= V[i] :
            curr[j] += curr[j - V[i]]
    prev = curr

print(prev[K])