4. [백준 13458번 / C++] 시험 감독

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

13458번: 시험 감독

 

쉬어가는 문제 느낌으로 풀었다.

 

먼저, 문제의 범위를 보자.

 

 

만약, B = C = 1이고 N = 1000000, 그리고 각 시험장에 있는 응시자 수 전부가 1000000이라면 필요한 감독관의 수는 한 시험장당 10^6명, 전체 시험장에서는 10^12이 될 것이다. 즉, 범위가 int형을 벗어난다.

 

long long 을 사용해야 한다!

 

이제 문제를 보면 간단하다. 각 시험장에는 반드시 '1명'의 총감독관이 있어야하므로, 시험장의 개수만큼 총감독관이 있는 것이고 이 총감독관이 감시하지 못하는 학생 수만큼만 부감독관을 투입시키면 된다.

 

즉, 어떤 시험장 i에 대해서 ((Ai - b) / c) + 1가 투입해야할 부감독관의 수이다! (+1을 해주는 이유는 C++의 정수형 연산은 정수부분만 계산결과로 내놓기 때문) 여기서 한 가지 더 고려해야하는 것은 Ai - b가 c로 나누어 떨어지는 경우에는 +1을 해줘선 안된다는 것이다.

 

예를 들어보자. 5명의 학생을 감시하기 위해 3명의 학생을 감시할 수 있는 감독관을 몇 명 투입시켜야하는가?

(5 / 3) + 1 = 2명 투입시켜야한다.

 

4명의 학생을 감시하기 위해 2명의 학생을 감시할 수 있는 감독관은?

(4 / 2) = 2명을 투입시켜야한다.

 

이를 구현한 코드는 다음과 같다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, a[1000004], b, c, ret;

int main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	cin >> b >> c;
	for(int i = 0; i < n; i++){
		if(a[i] <= b) ret += 1;
		else{
			if((a[i] - b) % c == 0) ret += (a[i] - b) / c;
			else ret += (a[i] - b) / c + 1;
			ret += 1;
		}
	}
	cout << ret << "\n";
}