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

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

2293번: 동전 1

 

문제

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

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

입력

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

출력

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

예제 입력 1 

3 10
1
2
5

예제 출력 1 

10

 

---

풀이

 문제를 정리하면, 동전이 N개가 주어지고, 각 동전들을 조합해서 K원을 만들 수 있는 경우의 수를 구해야 합니다.

우선, i원을 만들 수 있는 경우의 수를 담을 dp 리스트를 선업하고, 입력으로 주어진 동전들은 values에 담았습니다.

values = []
for i in range(n):
    values.append(int(input()))

# i원이 되는 경우의 수
dp = [0] * (k+1)
dp[0] = 1

 

이제 동전의 종류를 하나씩 늘려가면서 dp을 계산할 것입니다. 조건은 간단하게 현재 i원에서 동전의 가치를 빼서 0보다 크면 됩니다.

for value in values:
    for i in range(1, k+1):  # i원
        if i - value >= 0:
            dp[i] += dp[i-value]  # i-value원을 만드는 경우의 수만큼 추가

 만약에 동전을 사용할 수 있다면, dp[i]에 dp[i-value] 을 더해줍니다. 

이것의 의미는, i-value 원을 만드는 경우의 수만큼 추가해 주는 것입니다.

예를 들어 i = 8이고, value는 5라고 합시다. (5원짜리 동전)
그렇다면 i-value = 8 - 5 = 3인데, 우리는 5원이라는 동전을 사용해서 8원을 만드는 것이기 때문에 3원에 5원을 더하면 됩니다. 이때, 3원을 만드는 경우의 수는 이미 계산되어 dp[3]에 저장되었을 겁니다. 

 최종적인 구현은 아래와 같습니다.

Code

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
values = []
for i in range(n):
    values.append(int(input()))

# i원이 되는 경우의 수
dp = [0] * (k+1)
dp[0] = 1

for value in values:
    for i in range(1, k+1):  # i원
        if i - value >= 0:
            dp[i] += dp[i-value]  # i-value원을 만드는 경우의 수만큼 추가
print(dp[k])