03그리디 : 예제 3-1 거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 500, 100, 50, 10원 동전이 부한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일때 거슬러 줘야할 최소 동전의 갯수를 구하라.

단, 거슬러 줘야할 돈 N은 항상 10의 배수이다.

 

 

c++로 푼 결과물

#include <iostream>

using namespace std;

int main()
{
    int input, count = 0;
    cin >> input;
    
    for(int i = input; i > 0;) {
        if (i >= 500) {
            i -= 500;
        } else if (i >= 100) {
            i -= 100;
        } else if (i >= 50) {
            i -= 50;
        } else if (i >= 10) {
            i -= 10;
        } else {
            cout << "Error!";
        }
        count++;
    }
    cout << "cnt : " << count;
}