1엔, 4엔, 6엔의 3종류 동전으로 8엔을 지불한다. 큰 동전부터 쓸 수 있는 만큼 쓰는 탐욕 알고리즘으로 정했을 때의 개수와 최소 개수의 관계로 올바른 것은?

정답: B. 탐욕 알고리즘으로는 3개가 되어, 최소인 2개가 되지 않는다

탐욕 알고리즘에서는 먼저 6엔을 1개 쓰고, 나머지 2엔을 1엔 2개로 지불하므로 3개입니다. 그러나 4엔을 2개 쓰면 2개로 지불할 수 있습니다. 이처럼 탐욕 알고리즘은 그 시점에서 가장 좋은 선택을 쌓아 갈 뿐이므로, 동전의 조합에 따라서는 최적이 되지 않습니다. 동적 계획법으로 '0엔부터 8엔까지 각 금액을 지불하는 최소 개수'를 작은 금액부터 차례로 표로 만들면 반드시 최소 개수가 구해집니다. 덧붙여 1, 5, 10, 50, 100, 500엔 같은 일본 동전의 조합에서는 탐욕 알고리즘으로도 항상 최소가 됩니다.