프로그래머스 입국심사 with 파이썬

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

 

# 포인트

1. 이진탐색을 해야 하는 환경들

- n이 커서 완전탐색을 하지 못할 때

- 최소와 최대범위에서 타켓 값을 찾아갈 때

 

2. 이진탐색 시 중요 설정

- 탐색범위 : st와 end

투포인터와 다르게 이진탐색은 탐색범위를 st와 end로 설정하기 때문에 while st <= end에서 st와 end가 같을때 까지 반복문이 실행되도 됨

- 타켓 설정과 비교

ⓐ 쉬운 버젼 : 타켓과 mid를 곧바로 비교할 수

ⓑ 어려운 버젼 : mid를 이용한 값을 타켓과 비교할 수 cf. 입국심사문제에서는 심사 통과된 사람수인 p

def solution(n, times):
	times.sort()
    answer=0
	st, end=1, times[-1]
	while st <= end:
		mid=(st+end)//2
		p=0
		for t in times:
            p+=mid//t
            if p >= n: break
	
        if p >= n:
            answer=mid
            end=mid-1
        else :
            st=mid+1

    return answer