탁월함은 어떻게 나오는가?

[개념과 원리] 동전 거스름돈(coin change) 문제는 가게에서 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하여 거스름돈을 돌려주는 방법을 찾는 문제로, 동전 문제 또는 거스름돈 문제라고 한다. 사용 가능한 동전은 500원, 100원, 50원, 10원의 네 종류가 있다고 가정하자. 욕심쟁이 방법으로 동전 거스름돈 문제를 해결하는 가장 간단하고 효율적인 방법은 거스름돈의 액수를 초과하지 않는 조건하에서 단순히 액면가가 큰 동전부터 '욕심을 부려서' 최대한 사용해서 거스름돈을 만드는 것이다. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include using namespace std; ..