(파이썬) 백준 2293번 "동전 1"

---

# 답

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
dp = [0] * (k + 1)
dp[0] = 1

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

print(dp[k])

 

 

 

 

---

# 풀이

 

dp[n]을 'n원을 만들 수 있는 모든 경우의 수'이라고 할 때, dp 테이블을 일일이 채워보면 아래와 같습니다.

 

	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]
coin = 1	1	1 + 1	1 + 1 + 1	1 + 1 + 1 + 1	1 + 1 + 1 + 1 + 1	1 + 1 + 1 + 1 + 1 + 1
coin = 2		2	1 + 2	1 + 1 + 2 2 + 2	1 + 1 + 1 + 2 1 + 2 + 2	1 + 1 + 1 + 1 + 2 1 + 1 + 2 + 2 2 + 2 + 2
coin = 5					5	1 + 5

dp 테이블을 직접 채우다보면 아래와 같은 규칙을 발견할 수 있습니다.

n원을 만드는 경우는 (n - coin)원을 만드는 경우를 그대로 취할 수 있습니다.

(n - coin)원을 만드는 각각의 경우의 끝에 coin원을 딱 1개만 덧붙이면 n원이 되기 때문입니다.