Algorithm/Dynamic Programming

[DP] 백준 2293번 “동전 1” Python 풀이

운호(Noah) 2023. 12. 2. 19:38

문제 링크

풀이

  • 우선, 동전 1원으로 10을 만들 수 있는 경우의 수와

  • 동전 1, 2원으로 10을 만들 수 있는 경우의 수를 구함으로써 규칙을 찾을 수 있습니다.

  • 즉, 새로 갱신되는 dp[n]의 값은 이전의 dp[n]의 값에 dp[n - 현재 사용한 동전의 종류 크기] 가 됩니다.

  • 해당 규칙을 통해 1, 2, 5원으로 10을 만들 수 있는 경우의 수를 계산할 수 있습니다.

  • 추가적으로, dp[0]은 주어진 동전을 통해 0원을 만들 수 있는 경우의 수인데,

  • 아무 동전을 사용하지 않았을 때 0을 만들 수 있으므로, 경우의 수는 1입니다.

코드

import sys

n, k = map(int, sys.stdin.readline().split())

coins = []
for _ in range(n):
    coins.append(int(sys.stdin.readline()))

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

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

print(dp[k])

참고