[백준] G5. boj2293 동전1 / 분류 : DP 🙁

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

2293번: 동전 1

import sys
input = sys.stdin.readline

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

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

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

print(dp[k])

• dp 배열을 k+1 길이로 만든다. dp 배열은 각 인덱스에 맞는 금액을 만들 수 있는 경우의 수가 저장된다. dp[5]이면 5원을 만들 수 있는 경우의 수를 저장하는 것이다.
• dp[0]은 0원을 의미하는 것이 아니라, 동전 하나만 사용하는 경우를 의미한다. 
• 바깥의 for문은 coins를 돌면서 각 동전 금액별로 돌게 되고, 안쪽의 for문은 coin부터 k까지 돌게된다. 안쪽의 for문은 만들 수 있는 금액을 돌면서 계산하는 것이다.
• dp[i]  += dp[i - coin]으로 계산하는데, 예를 들어 예제로 설명하면, i가 9이고, 동전의 금액이 5원이면, 앞에서 1원과 2원을 사용하는 경우는 모두 계산된 것이고, 5원을 사용한 것은 i가 8, 즉 8원을 만들 수 있는 경우까지 계산된 것이다. dp[9] += dp[9 - 5]로 계산하는데, dp[9]일 때는 dp[4]. 즉 4원을 만들 수 있는 경우의 수를 1원과 2원으로만 구한 9원을 만들 수 있는 경우의 수에 더하는 것이다. 
• 1원과 2원만 사용해서 10원을 만들 수 있는 경우의 수에, 5원을 사용하는 경우는 1원과 2원으로 구한 5원을 만들 수있는 경우의 수와 같으므로, dp[10]도 마찬가지로 dp[10] += dp[10- 5]로 구할 수 있다.