Greedy 알고리즘

11047가 동전 0

 

1. 예제 -

{ 1 5 10 50 100 500 1000 5000 10000 50000 } 이 있을 때,

4200원을 만드는 최소의 방법은

1000 * 4

+ 100 * 2

이므로 총 6회이다.

 

2. 문제해결 -

 

[그리디한 해결전략] 순간의 최적해를 구한다.

(위 문제는 순간의 최적해가 최종 문제의 정답의 최적해인 경우라서 문제가 해결된다.)

 

가치가 가장 큰 동전을 최대한 많이 이용하고,

같은 방법으로 나머지 금액을 가치가 가장 큰 동전을 최대한 많이 이용해서

금액을 다 채울때 까지 반복한다.