13458번 시험 감독

백준 온라인 저지 13458번 시험 감독

---

문제 출처 : https://www.acmicpc.net/problem/13458

풀이 과정

우선 총감독관은 각각의 시험장에 1명만 존재할 수 있고, 부감독관은 여러명 존재할 수 있습니다. 

그러므로 맨 처음에 각 시험장에 있는 응시자의 수에서 총감독관이 감시할 수 있는 응시자의 수를 빼줘야 합니다.

총감독관이 감시할 수 있는 응시자의 수가 시험장에 있는 응시자의 수보다 크거나 같다면 부감독관은 필요하지 않을테니 종료해야 합니다.

이런경우 필요한 감독관의 최소 수는 1명이 됩니다.

그러나 총감독관이 감시할 수 없는 응시자가 존재한다면 부감독관을 채워 넣어야 합니다. 응시생들을 모두 감시해야 하기 때문이죠. 

부감독관의 수를 구하는 방법은 남은 응시자 수를 부감독관의 수로 나눠 몫을 구하면 그 몫이 부감독관의 수가 됩니다. 여기서 끝낼 것이 아니라 한가지 더 생각을 해봐야 합니다. 나머지를 어떻게 처리할 것인가 입니다. 

나머지가 0이라면 부감독관이 필요 없겠지만 0이 아니라면 감독하지 못하는 응시자가 남았다는 것이기 때문에 남은 응시자에 대한 부감독관이 한명 더 필요하게 되므로 +1을 해줘야 합니다.

주의할 점

감독관의 최소 수를 출력할 변수를 선언할 때 int로 했다가 낭패를 봤습니다.. 

나올 수 잇는 최대값을 생각해보면 시험장의 개수 100만 * 시험장 마다 필요한 감독관의 수 100만(시험장의 응시자 수가 100만일 때 총감독관이 감시할 수 있는 응시자의 수가 1명이고 부감독관이 감시할 수 있는 응시자의 수가 1명일 경우 감독관이 100만명 필요) 을 하면 1조가 됩니다.  

이 값은 int 범위를 벗어나는 값이므로 long long으로 선언해서 맞출 수 있었습니다.

 

소스 코드

 
#include<stdio.h>

using namespace std;

int person[1000000];

int main() {
	int n;
	scanf("%d", &n);
	
	long long total_cnt = 0;

	for (int i = 0; i < n; i++) {
		int t;
		scanf("%d", &t);
		person[i] = t;
	}

	int a, b;
	scanf("%d %d", &a, &b);

	for (int i = 0; i < n; i++) {
		total_cnt++;
		int diff = person[i] - a;
		if (diff > 0) {
			total_cnt += diff / b;
			if (diff %b > 0) total_cnt++;
		}
	}
	printf("%lld\n", total_cnt);
	
	return 0;

}