Boj 3079 입국심사 python

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

3079번: 입국심사

---

내 풀이

def count(time):
    cnt=0
    for i in range(n):
        cnt+=time//T[i]

    return cnt
T=[]    
n,m=map(int, input().split())
for p in range(n):
    k=int(input())
    T.append(k)

lt=1
rt=max(T)*m

while lt<=rt:
    mid=(lt+rt)//2
    if count(mid)>=m:
        res=mid
        rt=mid-1
    else:
        lt=mid+1
print(res)

-이분 검색 사용

 

-입국 심사 시간을 인자로 받아 몇 명을 심사할 수 있는지를 체크하는 함수를 작성

:직접적으로 문제에서 요구하는 것은 입국 심사 시간의 최솟값이나 이를 바로 구하기 어려우므로

역으로 가능한 시간들을 함수에 대입해서 범위를 줄여나가는 방식 선택

 

-count함수에서 나온 인원수가 m명보다 많으면 그 시간이 가능한 것이다. & 나온 인원수가 m명보다 적으면 그 시간은 불가능하다. 이에 맞추어서 범위를 조정하여 이분검색하면 풀리는 문제