[Algo Rhythm🕺💃]BOJ 13458 - 시험감독

문제 분석

시험장의 개수를 N(1 ≤ N ≤ 1,000,000), i번째 시험장에 있는 응시자의 수를 Ai(1 ≤ Ai ≤ 1,000,000) , 총감독관과 부감독관이 한 시험장에서 감시할 수 있는 응시자의 수를 각각 B, C(1 ≤ B, C ≤ 1,000,000)라고 하자.

그리고 i번째 시험장에 들어가야 하는 총감독관과 부감독관의 수를 각각 $n\_main_i$, $n\_sub_i$라고 하자.

 

총감독관은 각 시험장에 무조건 한 명 들어가야 하고 부감독관은 없거나 여러 명 있어도 된다. 따라서 i번째 시험장에서 필요한 감독관 수의 최솟값은 아래 부등식을 만족하는 가장 작은 $n\_sub_i$를 구하는 것과 같다.

$B\ +\ C \times n\_sub_i\ \ge A_i$

 

이를 통해 우리가 최종적으로 구해야 하는 답은 아래와 같다는 것을 알 수 있다. (이유는 모르겠지만 수식이 이상하게 나옵니다. 정확한 수식은 아래 원본문서를 참고하세요!)

$ans\ = \sum_{i=1}^N\ n\sub_i$ + $\sum{i=1}^N\ n\_main_i$

 

문제 풀이

문제 분석에서 도출한 부등식을 이항하면 아래와 같다.

$n\_sub_i\ \ge\ (A_i\ -\ B)\ /\ C$

 

이 부등식을 만족하는 가장 작은 $n\_sub_i$를 구하기 위해서는 $(A_i\ - \ B)$와 $C$의 관계에 대해 생각할 필요가 있다. $(A_i\ - \ B)$는 i번째 시험장에서 총감독관이 감독하는 응시자의 수를 제외한 나머지 응시자들의 수 즉, 부감독관이 감독해야 하는 응시자들의 수를 의미한다.

 

직관적으로 생각할때 부감독관의 수는 $(A_i\ - \ B)\ /\ C$ 임을 알 수 있다. 하지만 잘 생각해보면 부감독관이 감독해야 하는 응시자들의 수와 부감독관의 수가 나누어 떨어지지 않는 경우도 있다는 것을 알 수 있다. 그런 경우에 부감독관의 수는 $(A_i\ - \ B)\ /\ C + 1$이다. 이를 psuedo code로 표현하면 아래와 같다.

 

$if\ (A_i\ -\ B)\,\bmod\,C\ \ne\ 0,\ n\_sub_i\ =\ (A_i\ -\ B)\ /\ C\ + 1$

$else,\ n\_sub_i\ = (A_i - B)\ /\ C$

 

이때 두 가지 예외상황이 있다. 먼저 $A_i - B = 0$인 경우 즉, 총감독관 1명만으로 시험자들을 모두 감독할 수 있는 경우이다. 이때 $n\_sub_i = 0$이다.

두번째는 $A_i - B < 0$인 경우 즉, i번째 시험장의 응시자 수가 총감독관이 감독할 수 있는 인원보다 적은 경우이다. 이때도 마찬가지로 $n\_sub_i = 0$이다.

 

1번째부터 n번째 시험장까지 순회하며 $n\_sub$들의 합을 구하고 이를 $n\_main$의 합과 더하면 필요한 감독관의 최솟값을 구할 수 있다.

 

복잡도 분석

시험장의 개수를 N이라고 할때 시간복잡도와 공간복잡도는 아래와 같다.

 

시간 복잡도 : $O(N)$ - 각 시험장을 순회하며 $\sum_{i=1}^N\ n\_sub_i$을 구하기 때문에

공간 복잡도 : $O(N)$ - n개의 시험장의 응시자수를 모두 벡터에 저장하기 때문에

 

코드

 

문제 출처 및 원본문서

www.acmicpc.net/problem/13458

13458번: 시험 감독

www.notion.so/BOJ-13458-32f0acec8416417cb00d2a0a387a36cb

BOJ 13458 - 시험감독