[BOJ] 2293 동전1 (python)

문제

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

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

입력

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

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 $2^{31}$보다 작다.

풀이

1원에서 k원까지 만들 수 있는 각각의 경우의 수를 확인해서 푼다.
예시 입력으로 1,2,5원이 들어왔을 때 10원을 만들 경우의 수를 푼다고 생각하자.
1원 : 1
2원 : 1+1, 2

2원을 만들 경우는 두가지가 되는데 구하는 방법은 우선 2-c원(여기서 c는 동전의 값어치)을 만드는 방법을 전부 더해주면 된다.
2원을 만들려면 1원(2-1)을 만드는 방법에 1원을 더하는 방법이 하나 존재하기 때문에 2-1번째 cases의 값을 2번째 cases에 더한다.

코드 상에서 다시 설명하자면, i원을 만드려면 i-1원을 만드는 방법, i-2원, i-5원을 만드는 방법 각각을 다 더해주면 i원을 만드는 방법을 알 수 있다.
여기서 cases[0] = 1으로 설정하는 이유는 i원을 만들 때 i원의 가치를 가지는 동전이 있으면 그 동전을 하나만 사용하게 되고, i-i=0이기 때문에 cases[0]에 1을 넣어주는 것이다.

import sys

n, k = map(int, sys.stdin.readline().split())
coins = []
for _ in range(n):
    coins.append(int(sys.stdin.readline()))
cases = [0]*(k+1)
cases[0] = 1

for c in coins:
    for i in range(c, k+1):
        cases[i] += cases[i-c]
print(cases[k])