[백준] 2293번 동전 1

💡문제접근

• 테스트케이스를 예제로 점화식을 세워보았다.
• 1원을 이용해서 1 ~ 10원을 만드는 방법의 수는 모두 1가지가 나온다.
• 1, 2원을 이용해서 1 ~ 10원을 만드는 방법의 수를 단계적으로 살펴보자.
  1) 1원을 만들 수 있는 경우의 수 : 0
  2) 2원을 만들 수 있는 경우의 수 : 1
  3) 3원을 만들 수 있는 경우의 수 : 1.....
• 위와 같은 방식을 이용해서 점화식을 구성할 수 있다.

💡코드(메모리 : 31256KB, 시간 : 232ms)

import sys
input = sys.stdin.readline

n, k = map(int, input().strip().split())
coins = []
for _ in range(n):
    coins.append(int(input()))

dp = [0] * (k+1)
dp[0] = 1   # 0원을 만들 수 있는 방법의 수 : 1가지
for coin in coins:
    for i in range(coin, k+1):
        cnt = dp[i - coin]
        dp[i] += cnt
print(dp[k])

💡소요시간 : 18m