less than 1 minute read

문제

접근 방법

최대 사람 수 (m)가 1000000000인 것을 보고 사람에 대해서 iterate하여 최소 시간을 구하는 풀이는 제외하자고 생각했다.

알고있는 O(logn)의 알고리즘은 이진 탐색밖에 없기 때문에 이진 탐색을 활용해보자고 생각했다. 최대 시간은 $1000000 \times 10^9 = 10^{15}$이므로 logN으로 충분히 처리할 수 있었다.

여기까지는 생각했는데 mid = (start+end)/2 의 시간 안에 심사하는데 걸리는 시간들을 빠짐없이 배치해서 시간이 여유가 있는지 부족한 지에 따라 범위를 바꾸는 알고리즘을 생각하지 못했다.

각 심사대를 독립적으로 생각해서 각 심사대가 mid이라는 시간 내에 받을 수 있는 인원수의 합을 구하면, mid 시간 내에 받을 수 있는 총 인원수를 구할 수 있다.

정답 코드

import sys

input = sys.stdin.readline

n,m = map(int, input().split())
tests = []
for _ in range(n):
  tests.append(int(input()))

start = min(tests)
end = max(tests)*m

answer = 0

while start<=end:
  mid = (start+end)//2
  avail_ppl = 0
  for test in tests:
    avail_ppl += mid // test
  #여유로움
  if avail_ppl >= m:
    answer = mid
    end = mid-1

  #시간 부족함
  else:
    start = mid+1

print(answer)

You May Also Enjoy