문제
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.
예제 입력 1
3 10
1
2
5
예제 출력 1
10
문제 해결
점화식 찾기
예시를 보면 10을 1, 2, 5로만 구성해서 채워야한다.
나는 규칙이 분명 존재할 것이라고 믿었고, 일단 큰 수부터 구성을 해봤다.
k = 10
10
= 5+5
= 2 + 2 + 2 + 2 + 2
= 1 + 1 + 1 + ... + 1(한 종류로만 구성)
= 5 + 1 + 1 + 1 + 1 + 1
= 2 + 2 + 2 + 2 + 1 + 1
= 2 + 2 + 2 + 1 + 1 + 1 + 1
= ...(두 종류로만 구성)
= 5 + 2 + 2 + 1
= ...(세 종류로만 구성)
사실 일일히 적으면 10개가 나온다.
나는 '5+5'로 구성할 때, 5를 또 '2+2+1' 등으로 구성을 해서 규칙을 찾을 생각이었다.
하지만 문제 조건에서는 '2+2+1'과 '2+1+2'은 같은 경우로 보기 때문에 중복이 너무 많아 저런 방식으로는 찾을 수 없었다.
30분에서 한 시간 정도 고민을 했는데 답을 찾지 못해서 블로그를 참고했다.
블로그에서 본 원리는 다음과 같았다.
주어진 입력값을 이용하면, 10을 1, 2, 5로 구성해야한다.
그러면 dp[]를 1부터, 10까지 구성해보자.
1은 1로, 2는 1+1로 10은 1+1+...+1로 구성할 수 있다.
(코드로 따지면 for문이 10까지 다 돌고 나서)
그 다음에 2도 사용하는 것을 찾으면 0과 1은 사용을 못하기 때문에 넘어간다.
dp[2]는 1+1(이전의 dp[2]과 2다. 2는 새롭게 추가 된 것이기 때문에 dp[2]는 (이전)dp[2]+dp[2-2]가 된다. 2를 사용하는 dp[3]도 보자. 앞 전에 있었던 1+1+1에다가 2+1이 추가된다. dp1이나 1+2나 똑같은 한번으로 취급되기 때문에(1+2와 2+1은 같은 경우) (이전)dp[3]+dp[3-2]가 된다.
좀 더 큰 수를 본다면, 1,2까지 사용할 때의 dp[8]은 dp[8] + dp[8-2]가 된다. dp[6]은 이미, 1과 2로 이루어진 상태 일것이고 거기서 2만 추가한 것이기 때문에 dp[6] + dp8 이 된다.
따라서 점화식은 dp[i] = dp[i] + dp[i-c]이 된다.
표는 위 블로그 링크에 있다.
코드는 다음과 같다.
n, k = map(int, input().split())
coin = []
for i 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])```