주어진 동전의 집합에 대하여 가장 적은 개수의 동전으로 거스름돈을 만드… | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지

그리디로 최소 개수를 보장하는 동전 집합은 10, 50, 100, 200이다.
각 동전이 바로 아래 동전의 배수(50=10×5, 100=50×2, 200=100×2)이면, 큰 동전 하나를 작은 동전 여러 개로 바꿔도 개수가 줄지 않으므로 큰 동전부터 고르는 그리디가 최적이 된다.
10, 50, 60, 200: 100원을 그리디는 60+10×4로 5개를 쓰지만 50×2의 2개가 최적이다.
10, 40, 50, 100: 80원을 그리디는 50+10×3으로 4개를 쓰지만 40×2의 2개가 최적이다.
10, 50, 100, 130: 150원을 그리디는 130+10×2로 3개를 쓰지만 100+50의 2개가 최적이다.