[백준3079/골5] 입국심사 - Python

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

 

이분탐색 배워서 여름방학에 못풀었던 문제 다시 풀어봤다

 

1. 시간 지정해두고 그 시간 안에 몇명을 입국심사 할 수 있는지 계산

2. 인원이 남으면 high = mid - 1

3. 인원이 모자라면 low = mid + 1

 

# 실패 코드

N, M = map(int, input().split())  # 입국심사대 수, 상근이와 친구들 수
time = [int(input()) for _ in range(N)]

low = 1
high = 1000000000
result = 0

while low <= high:

    mid = (low + high) // 2

    people = 0

    for i in range(N):

        people += mid // time[i]

    if people < M:
        low = mid + 1
    else:
        high = mid - 1
        result = mid

print(result)

 

원인 : low랑 high 초기 값 잘못 설정해서 자꾸 틀렸다.

 

 

# 성공 코드

 

1. 시간 최솟값 : 가장 짧게 걸리는 입국심사대 하나 (min(time)

2. 시간 최댓값 : 가장 오래걸리는 입국심사대 하나에 상근이와 친구들 몰림 (max(time) * M)

 

N, M = map(int, input().split())  # 입국심사대 수, 상근이와 친구들 수
time = [int(input()) for _ in range(N)]

low = min(time)
high = max(time) * M
result = high

while low <= high:

    mid = (low + high) // 2

    people = 0

    for i in range(N):

        people += mid // time[i]

    if people < M:
        low = mid + 1
    else:
        high = mid - 1
        result = mid

print(result)

 

 

 

휴~ 개운하다~