[백준/Python] 2293번 - 동전1

문제

백준 2293번 - 동전1

해결 과정

테스트케이스를 예제로 점화식 세우는 과정

• 점화식: $dp[i] = dp[i - coin]$
• 1원으로 1 ~ 10원까지 만드는 경우의 수는 모두 1
• 1원, 2원으로 1 ~ 10원까지 만드는 경우의 수
  • 2원 만들기: 2가지
    • 1원으로 2원 만들기: (1,1)
    • 2원으로 2원 만들기: (2)
  • 3원 만들기: 2가지
    • 1원으로 3원 만들기: (1,1,1)
    • 1원을 만들 수 있는 경우에 2원을 추가: (1) + (2)
  • 4원 만들기: 3가지
    • 1원으로 4원 만들기: (1,1,1,1)
    • 2원 만들 수 있는 경우의 수에 2원을 추가: (1,1) + (2), (2) +(2)
  • 5원 만들기: 3가지
    • 1원으로 5원 만들기: (1,1,1,1,1)
    • 3원 만들 수 있는 경우의 수에 2원을 추가: (1,1,1) + (2), (1,2) + (2)
  • 6원 만들기: 4가지
    • 1원으로 6원 만들기: (1,1,1,1,1,1)
    • 4원 만들 수 있는 경우의 수에 2원을 추가: (1,1,1,1) + (2), (1,1,2) + (2), (2,2) + (2)

풀이

import sys

n,k = map(int,sys.stdin.readline().split())
coin = [int(sys.stdin.readline()) for _ in range(n)]

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

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

print(dp[k])