[백준] 시험 감독 (BufferedReader, StringTokenizer, 그리디 알고리즘, 13458번, Java)

▶ BufferedReader & StringTokenizer & 그리디 알고리즘 활용한 간단한 문제가 있어 정리해보고자 합니다.

 

문제설명

입력 & 출력

나의 풀이

 

이번 문제도 그리디 알고리즘을 활용하면 간단히 풀 수 있습니다.

 

문제에서 그리디 알고리즘을 활용할 수 있는 이유는 각 시험장마다 주 감독관과 부 감독관의 수를 최소화하여야 하기 때문입니다.

 

문제에서는 각 시험장의 응시자 수와 주 감독관, 부 감독관이 감시할 수 있는 인원이 주어집니다. 이때, 각 시험장에 필요한 주 감독관과 부 감독관의 수를 최소화해야 합니다.

 

주 감독관은 각 시험장마다 무조건 1명은 있어야 하므로, 주 감독관의 수는 응시자 수에 따라 변하지 않습니다. 이는 그리디 알고리즘의 조건인 "탐욕적 선택 속성"에 부합합니다.

 

따라서 주 감독관의 수를 먼저 고려하고, 남은 인원에 대해서만 부 감독관을 배치하는 것이 합리적입니다.

 

먼저 문제에서 나온 대로 입력을 받아주고, 감독관의 수(cnt)를 N으로 초기화 해줍니다. 이는 주석에서 볼 수 있듯이 각 시험장마다 무조건 1명의 총감독관이 있어햐하기 때문입니다.

 

그리고 for문에서 앞서 cnt 초기화에서 총감독관의 수는 미리 구한 것이기 때문에 해당 시험 응시자 수에서 총감독관이 감시할 수 있는 수를 빼줍니다. 

 

그리고 만약에 0보다 크면 "즉 총감독관 1명으로 다 감시할 수 없으면" 부 감독관을 배치해 줍니다.

 

28번째 줄을 예제로 보면 보다 쉽게 이해하실 수 있습니다.

3
3 4 5
2 2

 

위와 같이 입력이 주어졌을 때 28번째 줄에 들어서서는  3 4 5 ➡️ 1 2 3을 계산하게 됩니다.

 

1 % 2!= 0 ➡️ 0+1  = 1

2 % 2 == 0 ➡️ 1  = 1

3 % 2 != 0 ➡️ 1+1  = 2

 

따라서 총 7명의 감독관이 필요하게 됩니다.

 

참고 ❗

[JAVA] 입출력, BufferedReader, StringTokenizer

[Algorithm] 그리디 알고리즘(탐욕법, greedy, Java) 알아보기