백준 3079 : 입국심사

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

3079번: 입국심사

 

해결 방법 : 이분탐색

• M과 Tk가 1 <= M, Tk <= 1,000,000,000 으로 주어지므로, 모든 친구들이 입국심사를 통과하는데 걸린 시간 time은 최악의 경우(if N:1, M:max, T1:max) 1,000,000,000,000,000,000이 된다 ^^. 하지만 이분탐색을 사용하면 최악의 케이스라고 해도 60번 정도만 탐색하면 된다.
• 임의의 시간 time 동안 입국심사할 수 있는 인원을 기준으로 이분탐색하면 될 것이다.
  • time 동안 최대 통과 인원, check(time) = sum([time // t for t in T])  
• 유의할 점은 이분탐색시 target 인원 M을 max쪽에 포함시켜야 추가 작업 없이 값을 도출할 수 있다.
  • check(time) == M인 경우에 time 보다 작거나 같은 값이 최종값이 될 것이기 때문이다.

 

import sys
input = sys.stdin.readline

def solution(N, M, T):
    mn = 0
    mx = 10**18 # 주어진 조건에 따라 최악의 mx 설정

    def check(time): # time 동안 최대 몇명이 입국심사를 통과하는지 반환
        return sum([time // t for t in T])

    while mn < mx - 1:
        mid = (mn + mx) // 2

        if check(mid) < M:
            mn = mid
        else:
            mx = mid

    return mx

if __name__ == '__main__':
    N, M = map(int, input().split())
    T = [int(input()) for i in range(N)]
    result = solution(N, M, T)
    print(result)