백준 Gold5 - 동전 2 | kimjiil.github.io

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초 (추가 시간 없음)	128 MB	85430	26933	19109	30.305%

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

입력

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

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 1

3 15 1 5 12

풀이

가치의 합이 k원이 될때 사용된 동전의 수가 최소가 되도록 해야 된다. 이때 $DP[[c ...],k]$ 는 c동전을 사용해 k원을 만들 떄 사용한 최소 동전 갯수를 의미한다고 하자.

점화식으로 나타내면 다음과 같다.

DP([c_{1}, ... c_{i}], k) = \begin{cases} DP([c_1,...,c_{i-1}]) \quad if \quad k-c_{i} \le0 \\min(DP([c_{1}, ... c_{i-1}], \; k) , \; DP([c_{1},... c_{i}],\; k - c_{i}) + 1 ) \end{cases}

테스트 케이스로 주어진 예제로 dp 테이블을 만들어보면 아래와 같이된다.

K	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1,5	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3
1,5,12	1	2	3	4	1	2	3	4	5	2	3	1	2	3	3

다음 예제로 풀이를 하면 $DP[[1,5], 10] = Min(DP([1], 10), \; DP([1, 5], 10 - 5) + 1)$ 1, 5원 동전을 사용하여 10원을 만들 때 드는 동전의 가짓수는 1원만 사용해서 10원을 만드는 가짓수와 최소한 5원을 한번 이상 사용하여 1, 5원 동전을 사용해서 만드는 10원 동전의 가짓수 중에 작은 값을 사용하면 된다. 이때 최소한 5원을 한번 이상 사용하여 1, 5원 동전을 사용해서 만드는 10원 동전의 가짓수는 무조건 5원 동전을 사용했으므로 원래 금액에서 5원을 뺀 나머지 금액인 5원에서 1,5원을 사용하여 만든 가짓수인 $DP([1, 5], 5)$ 에다가 5원을 한번 사용했으므로 +1을 해주면 동전의 갯수가 나오게 된다.