백준 3079 입국심사

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

3079번: 입국심사

📌 해결순서

문제를 다 읽고, 이해는 되는데 도저히 어떻게 풀어야 할지 감이 안잡혀서 2일정도 붙잡으면서 풀이를 생각했던 문제다...

이게 이분탐색이라고??? 왜??? 이 생각을 계속 하게 만들었던 문제

근데 이분탐색으로 푸는게 맞다..다른 방법이 있을수도 있겠지만 전혀 생각나지 않는다..ㅋㅋ

 

이 문제는 랜선자르기

[백준] 파이썬 1654 : 랜선 자르기

문제와 굉장히 유사한 문제다.

 

1. start, end 값 찾기

일단 end 값은 쉽게 구할 수 있었다.

모든 사람이 심사가 가장 오래 걸리는 심사대에 가서 심사를 받으면 된다.

1번 예제라면 10 * 6 = 60

 

start 값에 대해서 생각을 해봤는데, 

먼저 심사하는데 걸리는 시간을 오름차순 정렬하고

모든 사람이 심사시간이 가장 짧은 심사대에 가서 심사를 하면 어떨까 생각해봤는데 틀렸다

1번 예제 같은 경우에 내 생각대로라면

start : 7 * 6 = 42 가 되지만

문제에서 요구하는 값보다 이미 크다

그래서, start 값을 가장 심사가 짧은 심사대의 시간으로 정하고 시작했다.

 

2. 시간의 최솟값 찾기

start, end 값을 정하고 이분탐색을 위해서 중간값을 계산해보면

이 중간값이 의미하는 것은 심사하는데 걸리는 총 시간이다

이 시간을 각 심사대의 심사시간으로 나누면 심사하는데 걸리는 총 시간동안 이 심사대에서 검사할 수 있는 사람의 수이다

 

3. 탐색범위 줄여가기

1번 예제에서 

start : 7 / end : 60 

mid = (start + end) // 2 = 33

33 동안 각 심사대에서 심사할 수 있는 사람의 수는

33 // 7 = 4

33 // 10 = 3

총 7명이다 

검사하려는 사람의 수보다 많으므로 시간이 널널함.. 즉 초과 됐음을 의미하고

현재 중간값보다 더 많은 시간에 대해서 탐색할 필요가 없으므로, end = mid - 1 로 탐색 범위를 줄여준다

 

start : 7 / end : 32

mid = (start + end) // 2 = 19

19 // 7 = 2

19 // 10 = 1

총 3명을 검사할 수 있다.

검사하려는 사람의 수 보다 적으므로 시간이 부족함을 의미하고

현재 중간값 보다 더 적은 시간이 대해서는 탐색할 필요가 없으므로, start = mid + 1 로 탐색 범위를 줄여준다

 

start > end 가 될때까지 반복해준다.

📌 코드

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    n, m = map(int, input().split())
    lst = [int(input()) for _ in range(n)]

    lst.sort()

    start = lst[0]
    end = lst[-1] * m
    ans = 0

    while start <= end:
        cnt = 0
        mid = (start + end) // 2
        for time in lst:
            cnt += mid // time

        if cnt < m:
            start = mid + 1
        else:
            ans = mid
            end = mid - 1

    print(ans)