[파이썬]백준 2293 동전

링크

백준 2293 동전

DP는 해도 항상 헷갈리는 것 같다.
점화식을 구해서 풀어야 했던 문제

정답 코드

import sys; input = sys.stdin.readline

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
#dp의 1번 인덱스는 합해서 1이되는 경우의 수 2번 인덱스는 합해서 2가되는 경우의 수 ...
dp = [0] * (k + 1)
dp[0] = 1 #아무것도 선택하지 않는 경우 한가지

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

print(dp[k])

알게된 것👨‍💻