[백준 알고리즘 풀이][C++] 13458: 시험 감독

기본 개념

https://www.acmicpc.net/problem/13458
원래 블로그 글을 내일 작성하려다가, 너무 쉬운 문제를 만나서 오늘 한번에 몰아쓰기로 결정했을 정도로 난이도는 낮은 문제이다. 백준 사이트 내의 정답률은 낮은 편인데, 다양한 케이스에 대처하지 못한 것이 그 이유로 보인다.

우선, 로직은 간단하다. 각 시험장에 주 감독관은 무조건 한명, 부감독관은 여러명이 가능하다.

즉, 각 방별로 우선 총감독관이 혼자 관리할 수 있는 방인지를 체크한 후, 아닐 경우에는 부감독관 개수를 더해주면 된다.

구현

int main() {
	unsigned n, b, c;
	vector<unsigned> spr;
	
	cin >> n;
	for(int i = 0 ; i < n ; i++) {
		int s; cin >> s;
		spr.push_back(s);
	}
	cin >> b >> c;
	
	long long total = 0;
	for(int i = 0 ; i < n ; i++) { // 방별로 루프
		if(spr[i] < b) total += 1; // 총감독관 혼자 커버 가능한 경우
		else { // 혼자 커버 불가능한 경우
			total += ((spr[i] - b) / c); // 총감독관이 커버하지 못하는 학생들을 부감독관이 커버
			if((spr[i] - b) % c != 0) total += 1; // 나머지가 있는 경우 한명 추가
			total += 1; // 총감독관 추가
		}
	}
	
	cout << total << endl;
}

더이상 어떻게 할 수 없을 정도로 난이도가 낮은 문제이다… 주석으로 모든 설명이 될 정도의 난이도.

한가지 주의할 점은 변수형이라고 생각하면 될 것 같다. 시험장 개수가 최대 1,000,000개, 응시자 수가 한 방에 최대 1,000,000명이기 때문에 모든 값이 최대로 주어지는 경우 1,000,000,000,000명의 응시자가 존재하게 된다. 한사람당 한명씩 감독한다고 생각하면 정답은 1,000,000,000,000로 int형의 범위를 뛰어넘게 된다.

따라서, 정답 변수인 total만 long long로 설정해두면 정답이 구해질 수 있다.

마무리

의외로 시간이 길게 책정되었다. 예상으로는 문제가 쉬운 만큼 예시를 어렵게 처리한 것으로 추측된다.

시간을 줄이기 위한 편법으로 입력을 받는 동시에 계산을 들어가게 하고 싶었지만, 중요한 변수인 b와 c가 나중에 입력되기 때문에 선택지가 없었다.

빠른 시간으로 푸신 분들의 코드를 살펴보면, 대부분 입출력의 time lag을 최소한으로 줄이는 방법을 선택한 것 같다. 전반적인 프로그램 로직은 차이가 없기 때문에 필자는 여기서 마무리하기로 하였다.