백준 Gold4 - 동전 1

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	4 MB	73277	35153	26798	47.937%

문제

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

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

입력

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

출력

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

풀이

동전의 가치가 $c_{1}, c_{2} ,..., c_{i} ,... ,c_{n}$ n개 있을 때 i번째까지 동전을 사용해서 k를 만드는 경우의 수를 $DP(i, k)$ 라고 한다. 이때 점화식은

$$DP(i, k) = \begin{cases} DP(i - 1, k) + DP(i, k - c_{n}) \quad, \; if \; (k-c_{n} \ge 0) \\ DP(i - 1, k) \quad else \end{cases}$$

이 된다. 예를 들어 1, 2, 5원 동전이 있을때 2원까지 사용하여 6원 동전을 만들때 점화식은 $DP(2, 6) = DP(1, 6) + DP(2, 6 - 2)$가 된다. 식을 풀이하면 1원 “만”을 사용해서 6을 만드는 경우의 수와 적어도 2원 동전을 적어도 “한번 이상” 사용하여 6을 만드는 경우의 수를 합치면 된다. 이때 2원을 한번 사용하면 6원에서 2원을 뺀 4원이 되고 1, 2원을 사용하여 4원을 만드는 경우의 수를 더하면 된다.

아래 표는 0부터 각 동전을 사용해서 만드는 경우의 수를 내려가면서 구한 것이다.

	0	1	2	3	4	5	6	7	8	9	10
0	1	0	0	0	0	0	0	0	0	0	0
5	1	0	0	0	0	1	0	0	0	0	1
5, 1	1	1	1	1	1	2	2	2	2	2	3
5, 1, 2	1	1	2	2	3	4	5	6	7	8	10
이때 동전의 가치는 정렬되지 않아도 상관 없다. 0원으로 0원을 만드는 방법은 무조건 1가지고 나머지는 무조건 0가지이다. 이때 동전의 가치로 만들 수 없으면 0이다.

test