[BOJ 2720] 세탁소 사장 동혁 - 그리디 알고리즘

문제 링크

• https://www.acmicpc.net/problem/2720

문제 요약

• 거스름돈을 최소 동전 개수로 거슬러주기 위해 Quarter($0.25), Dime($0.10), Nickel($0.05), Penny($0.01)의 개수를 구하는 문제
• 큰 단위부터 최대한 많이 사용하는 그리디 알고리즘 적용

접근 방법

• 그리디 알고리즘: 큰 단위의 동전부터 최대한 많이 사용
• Quarter(25센트) → Dime(10센트) → Nickel(5센트) → Penny(1센트) 순서로 나눗셈과 나머지 연산
• 각 단계에서 해당 동전의 개수를 구하고, 남은 금액을 다음 단계로 전달

풀이 코드

#include <iostream>
#include <string>
#include <vector>

int main() {
    int T(0);
    const int quarters = 25;
    const int dimes = 10;
    const int nickels = 5;
    const int pennies = 1;
    std::cin >> T;

    for(int i(0); i < T; i++) {
        int C(0);
        std::cin >> C;

        int numQuarters = C / quarters;
        C %= quarters;

        int numDimes = C / dimes;
        C %= dimes;

        int numNickels = C / nickels;
        C %= nickels;

        int numPennies = C / pennies;
        C %= pennies;

        std::cout << numQuarters << " " << numDimes << " " << numNickels << " " << numPennies << "\n";
    }

    return 0;
}

시간/공간 복잡도

• 시간: O(T) - T개의 테스트 케이스에 대해 상수 시간 연산
• 공간: O(1) - 고정된 변수만 사용