탐욕 알고리즘

/* 탐욕 알고리즘의 대표적인 문제로 거스름돈을 계산하는 문제가 있는데, 만약 거스름돈을 줄때는 최소의 동전 수로 거슬러 주며, 동전은 1원, 7원, 10원짜리의 동전이 있다고 가정합니다.  그리고 손님에게 14원을 거슬러 주어야 한다고 생각해봅시다. 이 문제를 탐욕 알고리즘으로 풀게되면, 매 순간마다 최선의 선택을 하려고 하기 때문에 10원, 1원, 1원, 1원, 1원으로 총 5개의 동전을 써서 손님에게 거스름돈을 건네줄 수 있을 것입니다. 그러나, 사실은 7원짜리 동전 2개로 거슬러 주게된다면 동전 2개를 사용해 건네주어서 최소의 동전 수로 거스름돈을 건네줄 수 있게 됩니다.  이제야 아실 것 같으신가요? 왜 탐욕 알고리즘이라고 불리냐면, 미래를 보지 않고 바로 앞에있는 것만 바라보기 때문에 붙여진 이름입니다.  */ #include <stdio.h> int coin[3] = { 10, 7, 1 }; int count[3]; int main() { int m, i = 0, f = 0; scanf("%d", &m); while (i < 3) { if (coin[i] > m) i++; else if (coin[i] < m) { m -= coin[i]; count[i]++; } else { f = 1; count[i]++; break; } } if (f) printf("%d원 동전은 %d개, %d원 동전은, %d개, %d원 동전은 %d개입니다.\n", coin[0], count[0], coin[1], count[1], coin[2], count[2]); else printf("해답을 구할 수 없습니다.\n"); return 0; }