[삼성코테기출문제] 시험 감독

시험감독

문제

여태 풀었던 기출 문제들 보다 다른 문제들에 비해 쉬운문제이다. 문제를 보자마자 Brute Force 라고 생각했다. 하지만 Brute Force 말그대로 야만적인 힘 이다. 완전탐색, 모든 경우의 수를 다 따져보는 것인만큼 시간복잡도와 공간복잡도를 생각을 많이 해야한다.

문제 풀이

입력 조건

시험장의 수 최대 100만, 응시자 수 최대 100만, 각 감독관이 감시 할 수 있는 수 최소 1이란 것을 모두 고려했을 때, 하나 하나 카운트 해 가며 계산 했을 때의 100만 x 100만이 된다. 그렇다면 처리해야할 계산은 1,000,000,000,000 1조개 이다. 컴퓨터가 1초에 처리할 수 있는 연산의 개수는 대략 1억개라고 생각해도 1000초가 된다. 따라서 시간초과가 나올 것이다. 그리고 나왔다…

그래서 이 문제의 Key Point 는 감독관이 감시할 수 있는 응시자 수를 한 번에 처리해야하는 것과, 범위자체가 큰 문제 이므로 답이 int 형의 범위도 초과할 수 있다는 것을 알아야 한다.

풀이 과정

1. 먼저 총 감독관은 각 시험장당 꼭 1명이 있어야하므로, 총 감독관의 경우 부터 생각하자. 총 감독관의 감시 수가 한 시험장의 응사지 수 보다 많을 수 있으므로 만약 그렇다면 Answer +=1만 해주면 된다.
2. 그렇지 않은 경우에는 총 감독관의 감시 수를 빼고 남은 응시자 수들과 부 감독관의 감시 수를 고려하여
   (남은 응시자 수) / (부 감독관의 감시 수)를 하여 Answer에 더해주면 된다.
   단, (남은 응시자 수) / (부 감독관의 감시 수)의 나머지가 0이 아니라면 부 감독관이 1명 더 필요하므로 +1을 해준다.

#include<iostream>

using namespace std;

const int MAX = 1000000;

int N, B, C;
int A[MAX];
long long  answer;

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> A[i];
	cin >> B >> C;
}

void Process() {
	for (int i = 0; i < N; i++) {
		if (A[i] >= B) {
			int d = A[i] - B;
			answer++;
			if (d >= 0 && d % C == 0) answer += d / C;
			else answer += d / C + 1;
		}
		else answer++;
	}
}
void Solution() {
	Input();
	Process();
	cout << answer << endl;
}
int main() {
	freopen("04.in", "r", stdin);
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	Solution();
	return 0;
}