[백준/Python] 2293번 동전1

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

 

정답코드

# 동전 1
# 복습횟수:0, 02:00:00
import sys
si = sys.stdin.readline
N, K = map(int, si().split())
dp = [0] * (K+1)
dp[0] = 1 # coin 3인 경우 dp[i-coin] 인 경우 1개를 추가해야 하므로 dp[0] = 1이되도록 
coins = []
for i in range(N):
    coins.append(int(si()))

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

print(dp[K])

 

풀이과정

 

2원을 탐색하는 경우 dp[4]의 빨간색부분과 dp[2] 부분을 보자

1+1, 2

1+1+2, 2+2

이 경우의 수는 2로 같다. 그냥 dp[2]에 2라는 탐색하는 coin을 추가한 것이기 때문이다. 따라서 dp[4] = dp[4] + dp[2] 이다.

 

5원을 탐색하는 경우 dp[6]의 빨간색 부분과 dp[6-5]를 보자 

1

1 + 5

dp[1]과 경우의 수가 같다

따라서 dp[6] = dp[6] (기존) + dp[1] (새로)이다.

 

이를 일반화하면

dp[i] = dp[i] + dp[i-coin]이 된다.