[Python] 백준 #3079- 입국심사

문제

---

3079번: 입국심사

q

코드

---

My answer

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
k=[int(input()) for _ in range(n)]

start,end=min(k), max(k)*m

while(start<=end):
    
    mid=(start+end)//2
    tmp=sum([mid//i for i in k])
    if(tmp>=m):
        end = mid-1
    else:
        start = mid+1
print(start)

Another answer

from sys import stdin

n, m = map(int, stdin.readline().split())
arr = [int(stdin.readline()) for _ in range(n)]

l, r = min(arr), max(arr) * m
ans = r

while l <= r:
    total = 0
    mid = (l + r) // 2

    for i in range(n):
        total += mid // arr[i]

    if total >= m:
        r = mid -1
        ans = min(mid, ans)

    else:
        l = mid + 1

print(ans)

풀이

---

우선 문제 아이디어를 생각하는게 너무 어려웠다.  이 문제를 브루트포스나 그리디로도 풀 수 있다고 하는데 그러면 시간초과가 난다. 따라서 이분탐색으로 해결했는데 아이디어는 다음과 같다.

단순하게 특정시간 t동안 몇명이 완료할 수 있는지를 계산해서 친구들 수보다 크면 t를 줄이고, 친구들수보다 작으면 t를 늘리는 방식이다.

예를 들어 기본 예시처럼 친구들=6명, 심사대=2곳(7초,10초) 이라고 할 때 이분탐색의 메인이 될 start, end를 설정해줘야한다. min값은 심사대 1개, 친구 1명일 때일 경우 심사대들 중 최소값 즉 min(7,10)->7이 나오게되고, max는 모두 오래걸리는 심사대에서 심사를 할 경우이므로, max(7,10)*친구들 수를 해준다. 

따라서 위의 예제에서는 start=7, end=60으로 이분탐색을 시작하게 된다. 아래 진행 과정을 살펴보면 이해가 빠를 것이다. 

1. start7, end=60 , mid=33

1. 33(mid)분이 지났을 때
2. 7분 심사대 = 3 // 7 = 4명 심사완료  + 10분 심사대 = 33 // 10 = 3명 심사완료
3. 총 4+3명=7명 > 6명(친구 수)
4. end=mid-1 

2. start=7, end=32 , mid=19

1. 19(mid)분이 지났을 때
2. 7분 심사대 = 19 // 7 = 2명 심사완료 + 10분 심사대 = 19 // 10 = 1명 심사완료
3. 총 2+1명=3명  < 6명(친구 수)
4. start = mid+1

3.start=20, end=32 , mid=26

1. 26(mid)분이 지났을 때
2. 7분 심사대 = 26 // 7 = 3명 심사완료 + 10분 심사대 = 26 // 10 = 2명 심사완료
3. 총 3+2명=5명  < 6명(친구 수)
4. start = mid+1

4. start=27, end=32, mid=29

1. 29(mid)분이 지났을 때
2. 7분 심사대 = 29 // 7 = 4명 심사완료 + 10분 심사대 = 29 // 10 = 2명 심사완료
3. 총 4+2명=6명  = 6명(친구 수)
4. end = mid-1

5. start=27, end=28, mid=27

1. 27(mid)분이 지났을 때
2. 7분 심사대 = 27 // 7 = 3명 심사완료 + 10분 심사대 = 27 // 10 = 2명 심사완료
3. 총 3+2명=5명  < 6명(친구 수)
4. start = mid + 1

6. start=28, end=27, mid=27

1. break 
2. start값 반환 

중요한점은 현재 값과 친구들 수가 같을 때 이게 최소값이 아닐 수도 있기때문에 end를 줄이면서 한번 더 확인해야 한다는 것이다(따라서 부등호를 신경쓰라는 말)

 

+)

another answer의 경우, ans라는 변수에 최소값인지 비교하면서 답을 비교하고 출력. 

이때는 반환값이 ans 내 풀이 같은 경우에는 단순하게 start를 반화하여 계산.