Overview
BOJ 3079 입국심사 Python 문제 풀이
분류: Binary Search (이분탐색)
문제 페이지
https://www.acmicpc.net/problem/3079
풀이 코드
from sys import stdin
def main():
n, m = map(int, stdin.readline().split())
t = [int(stdin.readline()) for _ in range(n)]
left, right = 0, max(t) * m
res = 0
while left <= right:
mid = left + (right - left) // 2
passed = 0
for time in t:
passed += mid // time
if passed < m:
left = mid + 1
else:
res = mid
right = mid - 1
print(res)
if __name__ == "__main__":
main()
이분탐색을 이용하여 모든 사람들이 심사가 끝나는 시간을 구한다.
모든 사람들이 심사를 마치는데 가장 오래 걸리는 시간은 max(t) * m 이다. 심사 시간이 가장 오래걸리는 심사대에서 모든 사람들이 심사를 거쳤을 때의 걸리는 시간이다. 따라서 left, right 값을 0과 max(t) * m으로 할당하고 while 루프를 돌리며 이분탐색을 한다. 이분탐색을 진행하면서 mid 시간 내에 모든 사람들이 심사대 통과가 불가능하다면, left에 mid + 1을 할당한다. 반대로 모든 사람들이 심사대 통과가 가능하다면, 결과 값으로 저장하고, right에 mid - 1을 할당한다.
