Q 14697 방 배정하기

💡 문제 요약 및 분석

방의 정원이 A, B, C 인 세 가지 타입의 방이 주어지고, 전체 학생 N명이 여기에 빈 침대 없이 들어가야 한다. 세 종류의 방을 전부 활용하지 않고, 하나 혹은 두 종류의 방만 사용해도 된다. 빈 침대 없이 배정이 가능할 경우 1, 불가능할 경우 0을 출력하자. A, B, C (1 ≤ A < B < C ≤ 50) N (1 ≤ N ≤ 300)

서브태스크

번호	배점	제한
1	3	입력 예시로 주어진 입력만 존재한다.
2	5	A = 1
3	14	B,C 는 A의 배수
4	78	원래의 제약조건 이외에 아무 제약조건이 없다.

💡 알고리즘 설계

1. 일단 가장 큰 수로 나누고, 나머지를 그 다음 큰 수로 나누면 될 것 같다. 이를 3번 반복하면 답을 얻을 수 있다.

💡 코드

import java.util.Arrays;

public class Main {

    public static int[] ary = new int[3];
    public static int N;
    public static int count = 2;

    public static void main(String[] args) throws Exception {
        for (int i = 0; i < 3; i++) {
            ary[i] = read();
        }
        N = read();

        cal(N);

    }

    public static void cal(int n) {
        int temp = n % ary[count];
        if (temp == 0) {
            System.out.println("1");
        } else {
            count--;
            if (count == -1) {
                System.out.println("0");
                return;
            }
            cal(temp);
        }
    }

    static int read() throws Exception {
        int c = 0, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(1)	O(1)