BOJ 13458 - 시험 감독

13458번: 시험 감독 (acmicpc.net)

 

N개의 시험장. i번 시험장에 있는 응시자 수 Ai명

감독관은 총감독관과 부감독관이 있다.

총감독관은 한 시험장에서 B명을 감시할 수 있고 부감독관은 C명을 감시할 수 있다.

각 시험장에 총 감독관은 오직 1명만 있어야 하고 부감독관은 여러 명 있어도 된다.

모든 응시생을 감시하기 위해 필요한 감독관 수의 최솟값은?

 

감독관 수의 최솟값이라는 것은 한 감독관이 최대한 많은 응시자를 감시해야 한다.

우선 총감독관은 시험장에 반드시 1명만 있어야 한다. 총감독관 혼자 해당 시험장을 감시할 수 있다면 부감독관은 투입하지 않아도 된다.

우선은 N명의 총감독관은 반드시 들어간다. 따라서 응시자 수에서 B를 일관적으로 뺀다.

그 후 남아있는 응시자 수를 C로 나눈다. 이때 올림 처리 한 것이 필요한 부감독관 수이다.

이 과정을 통해 O(N)의 시간복잡도로 해결 가능할 것이다.

import java.util.*;
import java.io.*;

public class Main {

    static FastReader scan = new FastReader();
    static int N, B, C;
    static int[] rooms;

    static void input() {
        N = scan.nextInt();
        rooms = new int[N];
        for (int i = 0; i < N; i++) {
            rooms[i] = scan.nextInt();
        }
        B = scan.nextInt();
        C = scan.nextInt();
    }

    public static void main(String[] args) {
        input();
        long answer = 0;
        answer += N;

        for (int i = 0; i < N; i++) {
            double remain = rooms[i] - B > 0 ? rooms[i] - B : 0;
            answer += Math.ceil(remain / C);
        }

        System.out.println(answer);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

여기서 정말 중요한 것이 하나 있다.

바로 필요한 감독관 수를 저장하는 answer 변수의 타입이다.

Ai가 최대 1,000,000이고 N도 최대 1,000,000이다.

때문에 총 필요한 감독관의 최대 수는 1,000,000 * 1,000,000 = 1,000,000,000,000이 된다. 이는 int 범위를 넘어서는 수이므로 long으로 처리해야 한다.