백준 13458 시험 감독

- 문제의 풀이법 자체는 쉽지만, 오답률이 높은 이유는 result에 int를 사용해서 일 것이다.

 

- 시험장이 1,000,000이고 응시생도 1,000,000 이고, 감독가능한 인원이 1,2 와 같은 소수일 경우 필요한 감독관 수는 어마어마하게 많아진다. 따라서 result의 자료형은 8byte 정수 자료형인 long long을 사용한다. int가 양수 21억까지 표현 가능하니 21억 x 2^16 하면 경 단위까지 표현이 가능해서 충분하다.

 

- 총 감독관이 감독할 수 있는만큼 각 시험장의 인원을 빼주고, 다시 순회하면서 부감독관들이 관찰 가능한 인원들을 활용하여 구해준다. 여기서, 이미 총 감독관 하나로 모든 인원이 감독 가능할 시, arr[i]값이 음수가 될 수 있으므로 예외처리를 해 준다. 시간복잡도는 O(N)

#include <iostream>
using namespace std;
int arr[1000000];
int main() {
	int n,b,c;
	cin >> n;
	long long answer = n; // 총 감독관 수를 더한다.
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	cin >> b >> c;
	for (int i = 0; i < n; i++) {
		arr[i] -= b;
	}
	for (int i = 0; i < n; i++) {
    // 총 감독관이 감독할 수 있는 인원보다 적다면 추가적인 인원이 필요 없으므로 continue
        if(arr[i] < 0) continue; 
		answer += arr[i] / c;
		if (arr[i] % c) answer++;
	}
	cout << answer << '\n';
	return 0;
}