[백준/C++] 13458번: 시험 감독

문제

총 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)

출력

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

 

풀이

각 시험장마다 총감독관은 1명씩 필수로 배치해야 하며, 총감독관만으로 감시가 충분한 경우 부감독관은 필요 없다.

1. 각 시험장마다 B(총감독관으로 감시할 수 있는 인원) 빼기

2. 응시자가 남은 경우 C(부감독관이 감시할 수 있는 인원)으로 나누기

3. 응시자 수가 C로 나누어 떨어지지 않는 경우 고려하기

 

+ 시험장의 개수, 각 시험장의 응시자 수가 최대로 주어지고 B와 C가 최소로 주어지는 경우, 결과가 int 범위를 넘을 수 있기 때문에 long long을 사용한다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, b, c;
    long long num = 0;
    cin >> n;
    vector<int> student(n);

    // 입력
    for (int i=0; i<n; i++)
        cin >> student[i];
    cin >> b >> c;

    // 연산
    for (int i=0; i<n; i++){
        int cnt = student[i];
        // 총감독관
        cnt -= b;
        num++;

        // 총감독관만으로도 충분한 경우
        if (cnt <= 0)
            continue;

        // 부감독관
        num += (cnt / c);
        if (cnt % c != 0)
            num++;
    }

    // 출력
    cout << num;
}