[BOJ] 백준 2293번 동전1 - 파이썬(Python)

문제

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

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

입력

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

출력

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

 

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

2293번: 동전 1

 

💡 풀이 및 코드

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

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

print(dp[k])

처음 접한 DP 문제의 유형이었다.

1, 2, 5라는 동전의 가치가 담긴 coin 리스트에 대한 반복문은 동전을 1원만 사용했을 때, 2원을 추가하여 1원과 2원을 사용했을 때, 5원을 추가하여 1원, 2원, 5원을 사용했을 때를 의미한다. dp[i]는 i라는 수를 만들 수 있는 경우의 수를 의미한다. 이때, 추가되는 동전(c)에 따라 dp[i]는 i가 c보다 크다는 가정 하에 i-c의 경우의 수(dp[i-c])를 누적해 주면된다. i-c을 만들\기 위한 동전의 조합들에 c를 더해주면 i가 되기 때문이다. 따라서, 점화식은 dp[i] = dp[i] + dp[i-c] 이다. 

아래의 경우의 수를 나타낸 표를 보면 이해가 쉬울 것이다.