Q 13458 시험 감독

💡 문제 요약 및 분석

시험장 N 개와 각 시험장의 응시자 수 A 가 주어졌을 때 필요한 총감독(B명 감시), 부감독(C명 감시) 인원을 구하면 된다.

💡 알고리즘 설계

✅ 핵심 아이디어 : 총감독은 무조건 1명이므로 ‘응시자 수 - B’, 부감독 수는 ‘남은 응시자 수 / C’ 의 몫을 올림하면 구할 수 있다.

1. 입력

   • 시험장 개수(int)
   • 응시자 수(int[])
   • 총감독, 부감독 감시 인원(int)

2. 연산

   • 시험장 개수만큼 반복한다. (최대 1,000,000번 반복)
   • 응시자 수 배열에서 i 번째 시험장의 응시자 수(num)를 가져온다.
   • (num - b / c) 값의 소수점 밑을 올림하면 부감독의 수. (누적합)
   • 시험장 하나 당 총감독 1명은 무조건 배정된다. (누적합)

3. 출력

   • 누적합한 count 변수를 출력한다.

💡 코드

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

    public static void main(String[] args) throws Exception {
        int n = read();
        double[] rooms = new double[n];
        for (int i = 0; i < n; i++) {
            rooms[i] = read();
        }
        double b = read();
        double c = read();

        int count = 0;
        for (int i = 0; i < n; i++) {
            double temp = rooms[i] - b;
            count++;
            if (temp == 0 || temp < 0) continue;

            double num = temp / c;
            int result = (int) Math.ceil(num);
            count += result;
        }

        System.out.println(count);
    }
}

💡 틀린 부분 분석

자료형 때문에 틀렸다. 시험장이 최대 100만개, 교실 하나 당 응시자 수가 100만명으로 최대로 가정하고, 감독관이 감독할 수 있는 인원을 최소 인원 1명씩으로 잡아 생각해보면 교실 하나에 필요한 감독관의 수는 최악의 경우 100만명이 되는데, 시험장이 100만개가 있으므로 이를 곱하면 수십억이 된다. int 의 범위는 21억이기 때문에 이를 초과할 수 있어 틀렸다. 이 경우 간단하게 count 변수를 long 으로 바꾸면 해결된다.

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

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

💡 느낀점 및 기억할 정보

• 범위 확인 : 지난번 경험으로 문제에서 2초 라는 시간이 주어졌을 때 2억번의 연산을 넘지 않도록 하면 통과할 수 있겠다고 생각했는데, 자료형의 범위를 잊었다… 구현하기 전에 범위에 대한 것을 체크한 것은 좋았지만 ! 자료형까지도 꼼꼼히 파악하자 !