No Limitation
[Binary Search] 입국 심사 - 프로그래머스 본문
https://programmers.co.kr/learn/courses/30/lessons/43238?language=python3
Example
6명의 사람이 있고
7, 10의 경우를 생각해보면
시간을 1≤ t ≤ 60(6명*10분) 범위 내에서 선택해서 적용한다 가정하면
예를 들어 중간 값인 30분을 할당할 수 있다고 하면
7의 경우 4명을 담당할 수 있고
10의 경우 3명을 감당할 수 있다.
따라서 각자 담당할 수 있는 사람의 합은 7명이고 이는 6명보다 더 큰 수가 된다
이 경우 시간이 많이 할당되므로 더 줄이는 방향으로 간다
반면 그 중간 값인 15분을 고려하면
7의 경우 2명을 담당, 10의 경우 1명을 담당하므로 3명을 총 담당이 가능하므로 6명을 주어진 시간에 다 담당 불가
따라서 시간을 더 늘리는 방향으로 갈 수 있다. → 이 search를 이분 탐색을 이용한다!
시도 1
def binary_search(L, U) :
mid = (L+U)//2
return mid
def make_sum(time, times, n) :
sums = 0
for i in times :
sums += (time)//i
if sums == n :
return sums ## 예시 5 [1, 5, 10], heuristic
def solution(n, times) :
answer = max(times)*n
mins = 1
maxs = max(times)*n
while maxs-mins != 1 :
time = binary_search(mins, maxs)
sums = make_sum(time, times, n)
if sums > n : maxs = time
elif sums < n : mins = time
else :
answer = min(time, answer)
maxs = time
return answer
여기 종료 조건을 max-min으로 했는데
binary search의 무한 루프를 막기 위한 조건이 확실치가 않음!
질문하기를 뒤져보니!
풀리지 않는 반례들이 존재!!
6
[4, 10]
이 경우의 답은 20인데
저 알고리즘으로는 절대 20이 나올 수 없음!
시도 2
그래서 저 경우를 Special Case로 다루어보고자 함!!
max와 min이 1차이가 나서 답을 슬슬 내야 되는 상황에서 최적의 해를 내지 못한느 경우는
그 경우 모든 인원을 수용할 수 있는 최소의 경우는 심사위원당 맡은 수의 사람의 합이 n보다는 큰 수 중 가장 작은 수여야 한다!
def binary_search(L, U) :
mid = int((L+U)/2)
return mid
def make_sum(time, times, n) :
sums = 0
for i in times :
sums += (time)//i
if sums == n : ## 대표 예제 n=5, [1, 5, 10]
return sums
return sums
def solution(n, times):
answer = max(times)*n
mins = 1
maxs = max(times)*n
while maxs-mins != 1 :
time = binary_search(mins, maxs)
sums = make_sum(time, times, n)
if sums > n : maxs = time
elif sums < n :mins = time
else :
answer = min(time, answer)
maxs = time
if answer == max(times)*n: ## 대표 예제 n=6, [4, 10], n=5, [1, 5, 10]
answer = maxs
return answer
원래 binary search는 Lower bound와 Upper bound 역전 내지 같아질 때가 종료조건이니
이것을 고려해주는 것이 중요
그리고 search할 때마다 폭을 줄여주기 위해
maxs = time-1
mins = time+1 같은
조치를 취해주었으면 더 좋았을듯
'프로그래밍' 카테고리의 다른 글
[Graph, BFS] 벽 부수고 이동하기 - 백준 (0) | 2022.02.12 |
---|---|
[Binary search] 랜선 자르기 - 백준 (0) | 2022.02.11 |
[Greedy] 멀티탭 스케줄링 - 백준 (0) | 2022.02.11 |
[DP] BOJ 거리 - 백준 (0) | 2022.02.04 |
[DP] 1, 2, 3 더하기 4 - 백준 (0) | 2022.02.04 |