[프로그래머스] 입국심사

https://programmers.co.kr/learn/courses/30/lessons/43238?language=python3

프로그래머스

---

[풀이]

이게 왜 이분탐색 알고리즘으로 분류될까? 라는 생각밖에 안들었고

문제를 딱봤을 때 이분탐색으로 어떻게 풀어야될지 감이 안잡혀서

작성코드를 제외하고, 푼사람들의 풀이과정을 살펴봤다.

 

여러풀이들이 있지만, 그나마 나에게 이해가 되는 풀이는

아래 블로그의 설명이다.

 

프로그래머스에서 제시된 예시로 이용하자면

N(사람수) =6, times=[7,10]

 

여기서 주의를 하자면 20분이됐을 때

4번 사람 심사 종료 후에 바로 6번을 심사하지 않고

1분 뒤인 21분에서 심사대 1에서 5번사람 심사 종료 후에 6번 사람을 심사하도록 한다.

그러면 진행시간이 28분일 때 6번사람의 심사가 끝난다.

심사대 1 (7분)		심사대 2 (10분)		진행시간
1번 사람		2번사람		0분
(1번종료) 3번 사람		2번사람		7분
3번 사람		(2번 종료) 4번 사람		10분
(3번 종료) 5번 사람		4번사람		14분
5번 사람		(4번 종료)		20분
(5번 종료) 6번 사람				21분
(6번 종료)				28분

변수 조건을 따져보자

심사받는 사람 수인 n은 1~10**9 명 이하이고

각 심사관이 한명을 심사하는데 걸리는 시간은 1분~10**9분 이고

각 심사관들은 심사하는데 걸리는 시간이 모두 다르다.

 

그렇다면 n명을 모두 입국 심사하는데

가장 빠른 시간은 1분이고,

가장 오래걸리는 시간은 max(times)*n 분이다.

 

left를 1, right=max(times)*n 으로 하고

평균 시간값인 mid분일 때 입국심사하는 사람의 수가 몇명인지를 구하고

그 사람 수가 6명보다 크거나 같은지, 작은지를 따지면서

이진탐색을 해야한다.

각 심사관이 mid분동안 심사완료시킨 사람수는  mid/time 명이다.

 

예산문제와 다르게 이진탐색 사용을 꽁꽁숨긴 것같다.

이진탐색 분류는 이진탐색알고리즘만 기억하면 쉽게풀리는 문제로만 알고있었는데

이 문제에서 해매는 내자신을 보니

아직도 더 많이 풀어야되는구나 라는 생각이 들었다.

 

 

[풀이 참고]

https://blog.naver.com/melon940925/221851960177

프로그래머스 - 입국심사(백준 3079번)

https://blog.naver.com/lhaayyy/221889539910

[프로그래머스/c++] 입국심사

---

[코드] Python3

def solution(n, times):
    left, right=1, max(times)*n
    
    while left<=right:
        mid=int((left+right)//2)
        
        cnt=0
        for time in times:
            cnt+=int(mid//time)
        
        if cnt>=n:
            right=mid-1
        else:
            left=mid+1
    return left

# 입국심사
import sys
from copy import deepcopy
input =sys.stdin.readline

def solution(n, times):
    times=sorted(times)
    left, right=1, n*max(times)
    
    while left<=right:
        mid=int((left+right)//2)
        cnt=0 #처음 대기중인 사람의 수

        #mid분동안 각 심사원들이 심사를 완료한 사람수를 구한다.
        for time in times:
            cnt= cnt+ int(mid//time)

        #mid분동안 심사완료한 사람수가 n명보다 크거나 같으면
        # left~(mid-1)분 에서 심사완료한 사람수를 구한다.
        if cnt>=n: 
            right=mid-1
            
        # mid분동안 심사완료시킨 사람수가 n명미만이면
        # mid+1~ right분 에서 탐색
        else: # tmp<n
            left=mid+1
    return left

n=int(input()) #입국심사를 기다리는 사람 수
times=[*map(int, input().strip().split())] #각 심사관이 한명을 심사하는데 걸리는 시간
print(solution(n, times)) #재귀를 이용한 이분탐색을 한다.