[백준 2293번] 동전1(파이썬)

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

2293번: 동전 1

문제는 짧지만 공부할 것은 많은 문제.

이 문제는 DP로 풀어야하는데

처음 보는 입장에서는 많이 난감합니다.

직접 그려보면서 이야기를 하겠습니다.

n, k = map(int, input().split())
c = []
dp = [0 for i in range(k + 1)]
dp[0] = 1
for i in range(n):
    c.append(int(input()))
for i in c:
    for j in range(1, k + 1):
        if j - i >= 0:
            dp[j] += dp[j - i]
print(dp[k])

 

저 같은 경우에는

예시코드만 보고

도저히 뭔소리인지 감이 안와

직접 손으로 그려봤습니다.

DP는 머리도 머리지만

손이 부지런한 것도 좋습니다.