Computer Science & Engineering

https://www.acmicpc.net/problem/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,000,000개이고 응시자 수가 1,000,000에 B, C가 각각 1인 경우 최대로 필요한 감독관의 수는 10^12이 된다. 약 2*10^9까지 표현할 수 있는 int형으로는 부족하다. 따라서 64비트를 이용하는 long long형을 사용해야한다. 풀이는 너무 간단하다. 각 시험장의 응시자의 수에서 B를 빼고 남은 인원이 0보다 클 경우 a에 C-1을 더하고 C로 나눈 몫만큼의 부감독관이 필요하다. 자세히 설명하자면 아래와 같다.

• 만약 응시자 수에서 B를 뺀 값이 4라고 하자. 
• C의 값이 5라고 하면 1명의 부감독관만 필요하다.
• 4에 C-1인 4를 더하면 8이므로 5로 나눈 몫은 1이다.
• 만약 5명이 남았다고한다면 5에 C-1인 4를 더하면 9이고 이를 5로 나눈 몫은 그대로 1이다.

즉 나누려고하는 값에서 1을 뺀 값을 나눠지는 수에 더하고 나누면 소수점에서 올림을 할 수 있다.

소스 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <deque>

using namespace std;

vector<int> arr;

int main() {
    int N; cin >> N;
    long long answer = 0; //정답
    for(int i = 0; i < N; i++) {
        int a; cin >> a;
        arr.push_back(a);
    }
    int B, C; cin >> B >> C;
    for(int a : arr) {
        a -= B; //총감독관이 감시할 수 있는 인원 빼기
        if(a > 0){ //그래도 수험생이 남아있으면
            a += (long long)(C-1); //C-1을 더함
            answer += (long long)(a / C); //C로 나눈 몫을 정답에 더하기
        }
        answer++; //총감독관 인원 더하기
    }

    cout << answer;
}

B를 뺀 값이 0보다 클 때 즉 수험생이 남아있는지 확인하는 이유는 만약 B를 뺀 값이 -5이고 C의 값이 4라고 한다면 C-1을 더하더라도 음수가 된다. 따라서 이상한 값이 나올 수 있기 때문이다.

채점 결과