[ 3079 ] [ 이분 탐색 ] 입국심사

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

3079번: 입국심사

 

---

풀이 과정

---

1. 보면 N값과 M값이 굉장히 크기 때문에 전수조사 하게 되는 경우 시간초과가 100% 날거라 생각됨.
2. 따라서, 친구들이 심사를 받는데 걸리는 시간을 기준으로 이분탐색을 진행함.
3. 범위는 최소 0, 최대 1000000000 * 10^9를 잡아주어야 한다. 
   • 이유는 입국심사대에 1명이 있으며, 친구들이 1000000000명, 그리고 걸리는 시간이 10^9인 경우를 고려
4. 중간값을 기준으로 중간값일때 심사받는 친구의 수가 M보다 크거나 같으면 시간을 줄여야 하므로 정답 저장후 왼쪽 구간, M보다 작은 경우는 정답을 저장하진 말고 오른쪽 구간을 진행하면 된다.
5. 저장된 정답을 출력해 준다.

---

소스 코드

---

 

import sys

input = lambda : sys.stdin.readline().rstrip()
N, M = map(int, input().split())
T = [int(input()) for _ in range(N)]

left = 0
right = (1000000000 * int(10e9)) + 1
answer = 0
while left <= right:
    mid = (left + right) // 2

    # 중간값일때, 심사받는 사람의 수 구함
    evaluated_people_count = 0
    for time in T:
        evaluated_people_count += (mid // time)

    # 심사받는 사람의 수가 M보다 작으면 시간을 늘려야 하므로 오른쪽 구간
    # M보다 크거나 같으면 시간을 줄여야 하므로 왼쪽 구간
    if evaluated_people_count >= M:
        answer = mid
        right = mid - 1
    else:
        left = mid + 1

print(answer)