파이썬 동전(BOJ 2293)

문제

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

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

입력

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

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

예제 입력 1

3 10
1
2
5

예제 출력 1

10

📝 풀어보기

여기서 dp에 들어간 숫자 dp[j]는 j원을 만들 수 있는 경우의 수를 의미한다. 즉, dp[5]는 4다.(5원을 만드는 경우의 수 4개)

예제를 예를 들어서 보자.

1, 2, 5원의 동전이 담긴 코인 주머니가 있다. 여기서 동전은 1원만 사용했을때, 1원과 2원을 사용했을때, 1, 2, 5원을 사용했을때의 경우의 수가 있고, 우리는 저 동전들을 사용해서 k값을 만족하는 경우의 수를 구해야한다.

1. 코인주머니속 코인(1, 2, 5) i를 순회한다.

2. 2원과 5원으로는 1원을 만들 수 없으므로 코인의 가치(i) 부터 가치의 합(k)까지 순회하면서 경우의 수에 해당하는 값만을 dp[j]에 집어넣어야한다.
3. j원에서 코인의 가치(i)를 뺀 값이 음수가 나오면 안되므로, j-i >= 0 인 가정하에 j-i의 경우의 수를 누적해준다.
4. 그렇게 누적한 dp리스트의 k번째에는 k값을 만족하는 경우의 수가 들어있다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coin = [int(input()) for i in range(n)]
dp = [0 for i in range(k+1)]
# dp[0]동전 하나를 사용하는 경우
# 즉 n이 1인 경우, 만약 n, k = 1, 2 라면 dp[2-2] = 1
dp[0] = 1

# dp[j] = j원을 만들 때 가능한 경우의 수
for i in coin:
    for j in range(i, k+1):
        if j-i >= 0:
            dp[j] += dp[j-i]
print(dp[k])