시험 감독

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

문제

총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다.

i번 시험장에 있는 응시자의 수는 A_i명이다.

감독관은 총감독관과 부감독관으로 두 종류가 있다.

총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다.

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

각 시험장마다 응시생들을 모두 감시해야 한다.

이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 각 시험장에 있는 응시자의 수 A_i (1 ≤ A_i ≤ 1,000,000)가 주어진다.

셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

출력

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

예제 입/출력 1

1
1
1 1

1

예제 입/출력 2

3
3 4 5
2 2

7

예제 입/출력 3

5
1000000 1000000 1000000 1000000 1000000
5 7

714290

예제 입/출력 4

5
10 9 10 9 10
7 20

13

추가 예제 입/출력 5

2
1000000 1
999999 1

3

추가 예제 입/출력 6

1
1
6 2

1

추가 예제 입/출력 7

3
3 4 5
3 1

6

추가 예제 입/출력 8

5
10 9 10 10 10
5 1

29

출처

• 문제를 만든 사람: baekjoon
• 문제의 오타를 찾은 사람: citizen, corea, jhpark1109
• 데이터를 추가한 사람: doju

알고리즘 분류

• 수학
• 사칙연산

통과된 코드

합계는 int의 범위를 넘어간다는 것과 계산중 -일 경우를 예외처리가 필요

#include <iostream>
using namespace std;

// 총 감시해야 할 시험장의 수 N, 각 시험장의 감독관 수 A, 부감독관 수 B, C를 저장할 변수
int N, A, B, C;

// 각 시험장의 응시자 수를 저장할 배열
int Room[1000000] = { 0 };

int main() {
    ios_base::sync_with_stdio(0); // C++의 표준 스트림의 동기화를 비활성화
    cin.tie(0); // 입력과 출력이 묶이지 않도록 함
    cout.tie(0); // 출력 속도를 높임

    cin >> N; // 총 시험장의 수 입력 받기
    for (int i = 0; i < N; i++)
        cin >> Room[i]; // 각 시험장의 응시자 수 입력 받기

    cin >> B >> C; // 총감독관 B와 부감독관 C의 감시 가능한 응시자 수 입력 받기

    long long int Sum = 0; // 필요한 감독관의 총 수를 저장할 변수
    for (int i = 0; i < N; i++) {
        int Temp = Room[i] - B; // 각 시험장의 응시자 수에서 총감독관이 감시 가능한 응시자 수를 뺌
        Sum += 1; // 총감독관은 무조건 한 명 필요
        if (Temp < 0)
            continue; // 총감독관이 감시 가능한 수보다 적으면 부감독관 필요 없음
        Sum += Temp / C; // 남은 응시자 수를 부감독관이 감시 가능한 수로 나눠서 추가
        if (Temp % C > 0)
            Sum++; // 나머지가 있으면 추가로 한 명의 부감독관이 필요
    }

    cout << Sum; // 필요한 감독관의 총 수 출력
    return 0;
}