[Python Algorithm] 동전1 BOJ #2293

문제

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

2293번: 동전 1

 

내 문제 풀이

import sys

n, k = map(int, sys.stdin.readline().strip().split())
coin = []
for _ in range(n):
    coin.append(int(sys.stdin.readline().strip()))
dp = [0 for _ in range(k+1)]
dp[0] = 1

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

print(dp[-1])

👉 DP 문제

점화식을 구하는 과정을 아래 그림으로 표현했다.

대표로 1, 2, 5 동전을 모두 사용하여 '6'을 만드는 과정을 서술했다.

6의 경우 (1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 2, 2), (2, 2, 2), (1, 5) 이렇게 5가지 경우의 수를 가지는데,

이는 기존에 1과 2만 가지고 6을 만들었던 경우의 수에, '6 - 5' 의 경우의 수를 더해주면 되는 것을 알 수 있다.

=> dp[i] += dp[i - c]

 

💡 피드백

점화식 도출 과정에서,, 알듯 말듯 하여 아주 오래걸렸다.

많이 풀면 나아지겠지ㅡ,?,,