13458번 - 시험 감독

1. 문제 정의

총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.

감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다.

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

각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

 - 입력 -

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.

셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

- 출력 -

 

각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수를 출력한다.

 

2. 문제 접근

처음에는 완전탐색 같아 dfs로 풀어야 하는줄 알았다. 그런데 시험장의 개수가 100만이고, 응시자 수도 100만이라 완전탐색으로 풀면 시간초과가 날거라는 것을 알지 못했다. 그래서 다시 구현 문제로 풀어 정답을 맞췄다.

 

3. 문제 풀이

1. 각 입력값을 받는다.

2. pro 함수를 정의한다.

 

4. 코드

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

public class 시험감독 {
    static StringBuilder sb = new StringBuilder();
    static int N, supervisor, assistant;
    static long result;
    static int[] applicant;
    static boolean[] visit, use;


    static void input() {
        FastReader scan = new FastReader();
        N = scan.nextInt();
        applicant = new int[N + 1];
        visit = new boolean[N + 1];
        use = new boolean[N + 1];
        for (int i = 1; i <= N; i++) applicant[i] = scan.nextInt();
        supervisor = scan.nextInt();
        assistant = scan.nextInt();
    }

//    static void dfs(int k, int cnt, int order) {
//
//        if (k == N) {
//            result = cnt;
//        } else {
//            for (int i = order; i <= N; i++) {
//                if (visit[i]) continue;
//                visit[i] = true;
//                applicant[i] -= supervisor;
//                ++cnt;
//
//                if (applicant[i] > 0) {
//                    int a = applicant[i] / assistant;
//                    int b = applicant[i] % assistant;
//
//                    if (a == 0) {
//                        ++cnt;
//                    } else {
//                        if (b > 0) cnt += 1;
//                        cnt += a;
//                    }
//                }
//                dfs(k + 1, cnt, ++order);
//            }
//
//        }
//    }
    static void pro(){
        long cnt = 0;
        for(int i = 1; i <= N; i++){
            applicant[i] -= supervisor;
            ++cnt;
            if (applicant[i] > 0) {
                int a = applicant[i] / assistant;
                int b = applicant[i] % assistant;

                if (a == 0) {
                    ++cnt;
                } else {
                    if (b > 0) cnt += 1;
                    cnt += a;
                }
            }
        }
        result = cnt;
    }

    public static void main(String[] args) {
        input();
        pro();
        System.out.println(result);
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

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

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        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());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

 

5. 회고

처음에 시간초과가 나서 완전탐색에서 구현 문제로 넘겼다. 그래도 정답이 틀려서 계속 찾아보다 도저히 모르겠어서 질문게시판을 봤더니 정답의 최대치가 문제였다. 만약 총감독관과 부감독관이 1 이고, 시험장의 갯수와 응시자의 수가 최대치인 100만으면 필요한 부감독관의 수는 100만 x 100만 만큼의 수가 필요하다. 이는 Integer 범위를 벗어나므로, 정답을 Long type으로 정의해줘야 에러가 안 난다. 이런 실수는 되도록이면 하지 않도록 노력하자.