11047: 동전 1

Reading time ~1 minute

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

동전을 적절히 사용해서 K라는 값을 만들면 된다.

직관적으로 생각하면, 가능한 동전 중 가장 큰 동전을 먼저 사용하면 최소한의 동전 갯수로 답을 만들 수 있다. 이 방법으로 풀면 통과한다.

하지만 이런 그리디 알고리즘이 왜 최적해를 찾을 수 있을까 ?

어떤 단계에서, 탐욕적으로 선택을 해서 최적해를 구할 수 있다는 것이다. 이 문제의 경우, 생각할 수 있는 최적해는 K>A를 만족하는 최대의 A 동전을 사용하는 것이다. 예제 1의 경우 4200>A를 만족하는 A는 1000이다. 이게 과연 최적해 일까?

다음과 같이 증명할 수 있다. 만약 A를 사용하지 않고 대신 B를 사용하여 (A>B) 구할 수 있는 최적해가 있다 하면,

B를 사용하는 경우 동전 N개를 사용하고, 나머지 부분문제 K-B*N을 풀면 된다.

하지만 여기서 A는 B의 배수이기 때문에 B*N=A*M이고, M<N 이기 때문에 B를 N개 사용하는 것보다 A를 M개 사용하는 것이 최적해라고 할 수 있다. 따라서 최대의 동전만을 사용하여 답을 구하는 것이 최적해라고 할 수 있다.

당연히 자명하다. A를 사용해 K 의 일부분을 계산하고, 나머지 액수도 동일하게 가장 동전을 적게 쓰게 구하면 된다.

간단히 풀 수 있는 문제지만 한번 증명해보면서 풀어 봤다. 끝 ~