BOJ 10162 - 전자레인지

문제

전자레인지는 버튼 A, B, C가 있다. 각 버튼을 누르면 각각 5분(300초), 1분(60초), 10초가 추가된다. 설정하려는 시간 T초가 주어질 때, 버튼을 최소로 눌러서 정확히 T초를 설정할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 설정하려는 시간 T(0 ≤ T ≤ 10,000)가 초 단위로 주어진다.

출력

버튼 A, B, C를 누른 횟수를 공백으로 구분하여 출력한다. T초를 정확하게 만들 수 없는 경우에는 -1을 출력한다.

예제

입력 1

출력 1

0 1 4

입력 2

출력 2

-1

풀이

핵심 아이디어: 큰 단위(300초, 60초, 10초)부터 최대한 많이 사용하는 그리디 전략을 사용한다. 10초 단위로만 나누어 떨어지므로, 마지막에 10으로 나머지가 0인지 확인하면 된다.

T가 300 이상이면 A = T / 300, T -= 300 * A
T가 60 이상이면 B = T / 60, T -= 60 * B
남은 T가 10의 배수가 아니면 -1 출력 (정확히 설정 불가)
10의 배수이면 C = T / 10, 결과 A B C 출력

각 단위로 나눈 뒤 남은 시간을 다음 단위로 처리하는 순차적 그리디이다.

코드

import java.util.Scanner;
 
public class Day355BOJ10162전자레인지 {
    static int T, A, B, C;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        if (T >= 300) {
            A = T / 300;
            T -= 300 * A;
        }
        if (T >= 60) {
            B = T / 60;
            T -= 60 * B;
        }
        if (T % 10 != 0) {
            System.out.println(-1);
        } else {
            C = T / 10;
            System.out.println(A + " " + B + " " + C);
        }
        sc.close();
    }
}

복잡도

시간: O(1) — 단위(300, 60, 10)별로 나눗셈/나머지 연산 3회
공간: O(1) — 상수 개수의 변수만 사용

문제