백준 13458번 시험 감독 :: 마이구미

이 글은 백준 알고리즘 13458번 "시험 감독" 을 풀이한다.

삼성 SW 역량 테스트의 기출 문제이다.

문제는 그리디(Greedy)하게 접근할 수 있다.

정답 비율과 삼성 기출 문제를 보면 쉽지 않게 느껴지지 않지만, 굉장히 쉬운 문제가 된다.

문제 링크 - https://www.acmicpc.net/problem/13458

그리디 알고리즘 - http://mygumi.tistory.com/121

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

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

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

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

각 시험장에는 총감독관은 1명밖에 없다.

우선적으로 총감독관이 감시할 수 있는 인원을 시험장에서 먼저 제외시킨다.

그 후, 나머지 응시생들에 대해 부감독관이 감시할 수 있는 인원을 나누기만 해준다면 문제는 해결된다.

for (int i = 0; i < n; i++) {
    result++;
    array[i] -= general;

    if (array[i] > 0) {
        result += Math.ceil(1.0 * array[i] / acting);
    }

}

주어진 한명의 부감독관이 감시할 수 있는 학생의 수 이하를 생각하면 되기 때문에 올림 처리를 해주면 된다.

무엇이 최적인지 파악만 할 수 있으면, 쉽게 빠르게 문제 해결이 가능하다.

다른 관련 그리디 문제들을 풀어보길 바란다. 

그리디 알고리즘 문제 풀이 - 그리디 문제 카테고리

Github - https://github.com/hotehrud/acmicpc/blob/master/SAMSUMG/13458.java

private void solve() {
    int n = sc.nextInt();
    int[] array = new int[n];
    long result = 0;
 
    for (int i = 0; i < n; i++) {
        array[i] = sc.nextInt();
    }
 
    int general = sc.nextInt();
    int acting = sc.nextInt();
 
    for (int i = 0; i < n; i++) {
        result++;
        array[i] -= general;
 
        if (array[i] > 0) {
            result += Math.ceil(1.0 * array[i] / acting);
        }
 
    }
    System.out.println(result);
}