궤도

문제 풀이 거스름돈 문제는 여러가지가 있지만 이 문제처럼 특수한 경우에는 그리디 알고리즘을 적용할 수 있다. 그 특수한 경우가 무엇일까? 바로 모든 동전들의 가치가 배수관계일 때이다. 만약 가치가 1, 7, 10원인 동전 3개가 있고 14원을 거슬러 줘야 한다고 하자. 그리디 알고리즘을 적용하면 10원 1개, 1원 4개 총 5개의 동전을 사용하지만 최적해는 7원 2개 총 2개의 동전을 사용하는 것이다. 아무튼 이 문제는 모든 동전들의 가치가 배수관계이니 맘편하게 그리디 알고리즘을 적용하자. 가장 가치가 큰 동전부터 가치가 작은 동전 순서로 거스름돈과 비교하면 된다. 소스코드 #include using namespace std; int coin[11]; int greedyCoin(int N, int K) ..