[BOJ][python] 2293. 동전 1

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

2293번: 동전 1

---

💡IDEA

동적계획법을 사용하는 문제이다.

1을 k번 더한 수를 합해서 점점 줄여가며 개수를 구하는 것은 알았으나, 점화식을 어떻게 써야할 지가 어려웠다.

입력받은 coins에서 동전의 가치 i를 사용하여 dp를 구성해야 하는데, i~k 사이의 수 j번째 값은 j 값 + (j-i) 값을 구할 수 있다.

쉽게 말하자면, i 값을 가진 동전을 사용하는 경우와, 사용하지 않는 경우를 더해서 계산한다고 생각하면 된다.

예를 들어 5를 1원과 2원짜리로 구성한다면, 5 = 1+1+1+1+1 = 2+1+1+1 = 2+2+1 인데, 2원을 사용하는 경우는 곧 5-2=3을 1원과 2원으로 구성하는 3 = 1+1+1 = 2+1 인 2가지 경우에 +2씩 해주는 것과 1원만 사용하는 1+1+1+1+1인 것을 더한 3가지 경우가 되는 것이다.

 

📌CODE

import sys
input = sys.stdin.readline

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

dp = [0]*(k+1)
dp[0] = 1
for i in coins:
    for j in range(i, k+1):
        dp[j] += dp[j-i]
        
print(dp[k])