[Python] 백준 3079번 : 입국심사

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

3079번: 입국심사

---

💡 문제 풀이

이분탐색 문제이다.

 

이번 이분탐색 문제에서 중심이 되는 값은 주어진 시간에 얼마나 많은 사람들이 통과할 수 있을까이다.

최대 범위(모든 사람이 가장 오래걸리는 심사대)에서 최소 범위(0)부터 이분탐색을 진행한다.

 

모든 입국 심사대를 확인하는데, 주어진 시간으로 얼마나 많은 사람들이 통과할 수 있는지만 보면 된다.

✔️ 느낀 점

이분 탐색은 항상 헷갈리는 문제이지만 어떤 값으로 비교할지 잘 선택만 하면 생각보다 금방 해결할 수 있다.

💻 코드

import sys
input = sys.stdin.readline

def init(n):
    global maxInput, taskTable
    
    for _ in range(n):
        num = int(input())
        taskTable += [num]
        maxInput = max(maxInput, num)

def countPassedByGivenTime(givenTime):
    passed = 0
    
    for task in taskTable:
        passed += givenTime // task
    
    return passed

def calcMinTime(people):
    minTime = 0
    maxTime = maxInput * people
    
    while minTime <= maxTime:
        middleTime = (minTime + maxTime) // 2
        passed = countPassedByGivenTime(middleTime)
            
        if passed < people:
            minTime = middleTime + 1
        else :
            maxTime = middleTime - 1
            
    return minTime

n, m = map(int, input().split())

maxInput, taskTable = 0, []
init(n)

minTime = calcMinTime(m)
print(minTime)