2720번. 세탁소 사장 동혁

아이디어

1. 거스름돈의 종류를 보면 25, 10, 5, 1입니다.

2. 큰 수가 작은 수의 배수 조합(25 = 2*10 + 1*5), (10 = 5*2), (5 = 5*1) 으로 이루어졌기 때문에 그리디 알고리즘으로 문제를 해결할 수 있습니다.

 

 

풀이 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int C = sc.nextInt();
            System.out.print(C / 25 + " ");
            
            C %=25;
            System.out.print(C / 10 + " ");
            
            C %= 10;
            System.out.print(C / 5 + " ");
            
            C %= 5;
            System.out.println(C);
        }
    }
}