[13458] 시험 감독

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

이번 문제는 시험 감독문제이다.

각 시험장마다 응시자들이 있고

그 응시자들을 감독할 총감독관과 부감독관이 있다.

총감독관과 부감독관은 감시할 수 있는 응시자의 수가 정해져있다.

시험장마다 총감독은 한 명뿐이고 부감독관은 여려명 있을 수 있다.

시험장의 개수(N)와 각 시험장의 응시자 수(Ai)

그리고 총감독관(B)과 부감독관(C)의 감시 인원이 인풋으로 주어진다.

예제를 확인하면 알 수 있지만

예제 입력 4 

5
10 9 10 9 10
7 20

예제 출력 4 

10

이 예제에서 출력 값이 10 이라는 뜻은

총감독관 한 명은 무조건 시험장에 있어야 한다는 뜻이다.

부감독관의 감시 응시생 수가 20명이므로 각 시험장당 부감독관 한 명만 있어도

모든 인원을 감독할 수있다. 하지만 답은 10명이므로

모든 시험장에 총감독관이 한 명씩 있다는 사실을 알 수있다.

문제 푸는 아이디어는

시험장 마다 총감독관의 감시 응시생 수(B) 빼준후

남은 응시생이 있다면 부감독관의 응시생 수(C)로 나누어 준 후

몫을 더해준다. 만약 나눈 후 0으로 나누어 떨어지지 않는다면 한 명의 부감독관이 더 필요하다는 뜻이므로

1을 더 더해주면 된다.

이 문제의 함정은 딱 하나이다.

바로 범위.

백만 개의 시험장에 백만 명의 응시생이 있고

총감독관과 부감독관 모두 감시 응시생 수가 한 명 이라면

필요한 총 감독관 수는 10^6 * 10^6 이므로 10^12이 된다.

즉 int범위로는 커버가 안되므로

출력 값은 long long으로 해주어야 한다.

끝.

#include<cstdio>
using namespace std;
int arr[1000100];
int main(){
    int n, b, c;
    long long cnt;
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d", &arr[i]);
    }
    scanf("%d %d", &b, &c);
    cnt = n;
    for(int i=0; i<n; i++){
        arr[i] -= b;
        if(arr[i] > 0){
            int t = arr[i] / c;
            int m = arr[i] % c;
            cnt += t;
            if(m){
                cnt++;
            }
        }
    }
 
    printf("%lld\n", cnt);
 
    return 0;
}