백준 2720 세탁소 사장 동혁 / C++

문제 : 2720

풀이 point

손님이 받는 동전의 개수를 최소로 하는 것이 관건이다.
다만 부동소수로 계산할시 오차가 발생할 수 있기 때문에
쿼터, 다임, 니켈, 페니의 단위를 센트로 바꾼 후 계산하는 것이 좋다.

풀이 방법

동전의 개수를 최소화 하기 위해서는 가장 큰 수로 나눈 후 그 나머지들을 작은 것들로 채워나가야된다. 가장 큰 값은 쿼터 -> 다임 -> 니켈 -> 페니 순이므로 이 순서대로 거스름돈을 채워나간다.

코드

//백준 2720, 세탁소 사장 동혁
#include <iostream>

int change[4];

int main(){

    int T; int N;
    std::cin >> T;
    while(T--){
        int change[4] = {0};
        std::cin >> N;
        if(N >= 25){
            change[0] += N/25;
            N -= (N/25)*25;
        }
        
        if(N >= 10){
            change[1] += N/10;
            N -= (N/10)*10;
        }
        if(N >= 5){
            change[2] += N/5;
            N -= (N/5)*5;
        }
        if(N >= 1){
            change[3] += N/1;
            N -= (N/1)*1;
        }
        for(int i{0}; i<4; ++i){
            std::cout << change[i] << ' ';
        }
        std::cout << '\n';
    }

    return 0;
}