[ETC] BOJ 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. 총감독관의 수용인원보다 적은 경우 1을 더한다.

 

2. 부감독관의 수용인원으로 나누어 떨어지는 경우 나눈 수에 1을 더한다.

 

3. 부감독관의 수용인원으로 나누어 떨어지는 경우 나눈수에 2를 더한다.

 

 

 

이 문제는 사실 문제를 설계하는 것보다

공간 복잡도를 잘 분석해서 적절한 변수를 사용하는 것이 핵심이다.

 

 

 

최악의 경우 시험장이 10^6이고 모든 방에 학생이 10^6 명 있는데

감독관의 수용인원은 모두 1이라고 생각해보자.

 

 

 

이렇게 되면 감독관이 10^6 x 10^6 명인 10 ^12 명이 필요하게 돼서 

int의 최댓값을 넘어 오버플로우가 발생한다. 

 

 

 

이 부분을 잘 판단해서 long long 의 자료형을 사용하는 것이 핵심이다!

 

 

코드

---

#include <iostream>

using namespace std;
int room[1000001];
long long cnt = 0;

int main(){
	int n, b, c;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> room[i];

	cin >> b >> c;

	for (int i = 0; i < n; i++) {
		if (room[i] <= b) cnt++;
		//총감독관 1명
		else {
			int k = room[i] - b;
			if (k % c == 0) cnt += k / c + 1;
			// +1 은 총감독관
			else cnt += k / c + 2;
		}
	}
	


	cout << cnt << '\n';


	return 0;
}