Archive horanglab

백준 13458번 (시험 감독, C++) [BAEKJOON]

#C++ #수학

문제

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

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 99556 31008 23090 29.650%

총 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

plaintext 
1
1
1 1
plaintext 
1

예제 입/출력 2

plaintext 
3
3 4 5
2 2
plaintext 
7

예제 입/출력 3

plaintext 
5
1000000 1000000 1000000 1000000 1000000
5 7
plaintext 
714290

예제 입/출력 4

plaintext 
5
10 9 10 9 10
7 20
plaintext 
13

추가 예제 입/출력 5

plaintext 
2
1000000 1
999999 1
plaintext 
3

추가 예제 입/출력 6

plaintext 
1
1
6 2
plaintext 
1

추가 예제 입/출력 7

plaintext 
3
3 4 5
3 1
plaintext 
6

추가 예제 입/출력 8

plaintext 
5
10 9 10 10 10
5 1
plaintext 
29

알고리즘 분류

출처

접근 방법

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

통과된 코드

cpp 
#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;
}