[BOJ] 13458번 시험 감독 (Python) [삼성 SW 역량 테스트 기출 문제]

문제

https://www.acmicpc.net/problem/13458

풀이

시험장의 개수 N이 1,000,000이므로 $O(N)$ 이나 $O(NlogN)$으로 풀어야겠다고 생각했다.
여기서 핵심은 부감독관을 배치할때 for문이나 while문을 돌리면서 하면 $O(N^2)$이 되므로 시간초과가 난다는 점이다. 아마 정답률이 낮은 이유도 이 부분 때문이지 않을까 싶다.

divmod를 사용해서 몫과 나머지를 뽑아서 수식하나로 $O(1)$로 부감독관을 배치하도록 했다. 이때, 구체적인 예시를 적어서 코드를 어떻게 짤지 생각하니 빠르게 접근할 수 있었다. 그런데 더 나은 수식이 존재할 것 같아서 찾아봐야겠다.

N = int(input())
people_cnts = list(map(int, input().split()))
B,C = map(int, input().split())

ans = 0 
for people_cnt in people_cnts: # 1,000,000
  # 총감독관
  ans+=1
  people_cnt -= B
  
  # 부감독관
  if people_cnt > 0:
    quotient, remainder = divmod(people_cnt, C)
    ans += quotient
    if remainder: # 나머지가 0이 아니면
      ans+= 1

print(ans)