[백준] #3079 - 입국심사

2023/7/17

골드5

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

3079번: 입국심사

 

 

🔎 분석

이분탐색 문제를 풀려고 선택한 문제.

이분탐색 아니라고 생각하고 우선 컨셉을 잡으려고 했다.

전체 로직은 인원 수를 각 입국심사대에 적절히 분배하여 최소 시간이 되도록 하는 것이었다.

 

어떤 것을 l, r로 정하고 mid를 구할지가 가장 큰 고민이었다.

꽤 오래 고민하다가(거의 1시간..?) 기다리는 시간도 시간으로 포함된다는 점에서 시작해서 특정 시간 값을 mid로 하고, 그 mid로 각 입국심사대의 시간을 나눈 몫인 인원 수가 전체 인원 수가 되도록 해야겠다고 생각했다.

 

✏️ 과정

그래서

if mid//각 입국심사대 시간을 다 더한 값 < 전체 인원 M: 
         l = mid + 1 # 더 큰 값을 mid로
else:
	r = mid - 1 # 더 작은 값을 mid로

이렇게 구현하였다.

한 번에 맞았습니다가 나왔다 !!! 드디어! 마찬가지로 재귀로 이분탐색을 적용하고 예제를 돌렸다.

 

 

💻 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
time_list = sorted([int(input()) for _ in range(N)])

l = 0
r = time_list[0]*M

def binary_search(a, l, r, M, result):
    mid = (l+r)//2

    if l<=r:
        total_people = 0
        for time in a:
            total_people += mid//time
        
        if total_people < M:
            binary_search(a, mid+1, r, M, result)
        else:
            result = min(result, mid)
            binary_search(a, l, mid-1, M, result)
    
    else:
        print(result)

binary_search(time_list, l, r, M, r)