[BOJ] 13458. 시험 감독

https://www.acmicpc.net/problem/13458

13458번: 시험 감독

각각의 시험장에 총 감독관 1명 혹은 여러 명의 부감독관이 있는데 각 시험장마다 응시생들을 모두 감시해야 한다.

이때, 필요한 감독관 수의 최솟값을 구하는 문제이다.

 

문제를 읽고 총감독관이 없어도 되는건가? 하고 헷갈렸는데 1명은 있어야 맞는 것 같다.

그러므로 일단 각 시험장에서 총감독관이 감시할 수 있는 B명을 빼준다. 그리고 남은 인원을 부감독관이 감시하면 된다.

남은 인원 / 부감독관이 감시할 수 있는 인원

을 해주었을 때 나머지가 존재 할 수 있으므로 이런 경우에는 1을 더해준다.

 

 

이 문제에서 제일 중요한 점은 감독관의 수를 저장해 줄 변수를 long long으로 선언해주어야 한다는 것이다.

 

• 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
• 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.
• 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

범위가 위와 같기 때문에 최악의 경우

B와 C가 1 , N이 1,000,000 , 모든방의 응시자 수 1,000,000 라면

1,000,000 (시험장의 개수) * 1,000,000 (응시자의 수) / (1+1) (b와 C)

가 되므로 int의 범위를 넘어가버리기 때문에 long long으로 선언해주어야 한다.

 

문제가 어렵지 않음에도 불구하고 정답률이 낮은건 이 부분 때문인 것 같다.

 

#include <iostream>
using namespace std;
int n;
int a[1000001];
int b, c;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
 
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> b >> c;
    
 
    //시험장의 개수 만큼 총감독관이 존재한다.
    long long ans = n;
    
    for (int i = 0; i < n; i++) {
        //총감독이 감시할 수 있는 인원을 제외
        a[i] -= b;
 
        //총감독이 i번쨰 시험장의 사람들을 모두 감시할 수 있으면
        //부감독관이 더 필요없으므로 넘어간다.
        if (a[i] <= 0) continue;
 
        //남은 인원을 부감독관이 감시할 수 있는 수로 나눠서 몇명이 더 필요한지 구한다.
        ans += a[i] / c;
 
        //나누어 떨어지지 않는 경우 1명이 더 필요하다.
        if (a[i] % c != 0) {
            ans += 1;
        }
    }
    
    cout << ans;
    return 0;
}