탐욕법 Greedy Algorithm (feat.컴공선배)

모든 문제에 적용할 수 없다

초반에는 최악의 선택지로 보이지만 결국에는 더 나은 결과로 이어지는 선택지인 경우가 있는 문제에는 그리디를 적용할 수 없다

 

이 문제는 그리디 문제로 풀 수 있지만

 

이 문제는 그리디로 풀 수 없다

 

두 문제의 차이점은 숫자의 배수가 그 다음으로 큰 숫자가 될 수 있는지의 유무이다

10,50,100,500은 모두 작은 수의 배수로 구성이 가능하니 500을 가장 많이주고 그다음 100을 주는 방식이 가능하지만

400,500의 경우에는 배수가 안되고 그 말은 1200원처럼 400으로만 가능한 경우가 발생한다는 것이다

 

즉 그리디의 문제는 다음과 같다