★Binary Search Advanced I - 2 Solved★

★ 2295 세 수의 합 ★

 

import sys
input=sys.stdin.readline

def binary_search(target, l):
    start,end=0,len(l)-1
    while start<=end:
        mid=(start+end)//2
        if l[mid] == target:return True
        elif l[mid] > target:
            end=mid-1
        else:
            start=mid+1
    return False



#O(N^2logN)
N=int(input())
U=set()
for _ in range(N): U.add(int(input()))
L=list(U)
L.sort()

two=[]
for x in range(len(L)):
    for y in range(x,len(L)):
        two.append(L[x]+L[y])
two.sort()
for x in range(len(L)-1,-1,-1):
    for y in range(0,x):
        if binary_search(L[x]-L[y],two):
            print(L[x])
            sys.exit()

 

🎆 (중복해서) 세 수의 합이 집합 U에 존재하는데, 그 중 최댓값 출력 문제로, 이분탐색 응용문제. 무언가 두 개를 묶고 나머지 한 쪽의 값을 이분탐색으로 찾아내는 유형

 

🎆

① two []에 두 개의 합 저장

② two list에서 이분탐색 해야 하므로 정렬 

③ 세 수의 합 후보를 최댓값부터 차례대로 two list에 binary search 탐색 → 찾으면 세 수의 합 최댓값 바로 찾았으므로 sys.exit()

(무조건 존재하는 경우만 있으므로 없는 경우 고려 x)

 

🎆 세 수와 합까지 O(N^4) 시간 복잡도를 먼저 두 수의 합을 만들고 거꾸로 전체에서 한 수를 뺀 결과가 두 수의 합에 있는 지(binary search) 알아보는 시간 복잡도는 [전체에서 한 수를 뺀 결과 만들기 O(N^2)] 곱하기 [binary search 시간복잡도(O(log(N^2)) - two list 길이 N^2]

: 따라서 최종 시간 복잡도는 O(N^2log(N^2))로 O(N^2log(N))만에 구할 수 있다.

---

★ 3079 입국심사 ★

 

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
Ts=[int(input()) for _ in range(N)]
Ts.sort()
start,end=min(Ts),M*max(Ts)

while start<=end:
    mid=(start+end)//2
    total=[mid//T for T in Ts]
    total_T=sum(total)
    if total_T >= M:
        ans=mid
        end=(mid-1)
    else:
        start=mid+1

print(ans)

 

🎆 최적의 최솟값 시간을 찾기 위해 최솟값 + 최댓값 시간 넣고 이분탐색 돌리는 전형적인 문제

 

🎆

① start, end 설정: start는 심사대 중 가장 짧게 걸리는 시간 / end는 가장 길게 걸리는 심사대에 모든 사람들 다 줄 선 최댓값 시간

② mid 구하며 binary search 진행

③ mid로 구한 시간 내에 각 심사대별 수용 가능 최대 인원 수 모두 더한 합이 인원 수 M보다 크거나 같다면 mid를 줄이기 위해 end = mid - 1(이 때는 문제의 조건을 만족하므로 ans에 mid 업데이트) / 그 반대라면 mid를 키우기 위해 start = mid + 1

④ 최종적으로 while문 끝났을 때 마지막으로 업데이트한 ans 출력 

→ M명을 모든 심사대에 각각 넣어서 가능 case를 일일이 찾는 것보다. 반대로 생각해 가능 시간을 mid로 탐색해 나가면서 각 여권 심사대에 해당 가능 시간 내에 수용 가능 인원을 쭉 구해 최종 더한 결과가 M명을 넘는 지 / 안 넘는지에 따라 이분탐색 진행이 바람직(O(logN + log(N)*N))

 

ex) 위 예시 (1) mid 30이라면 수용 가능 인원보다 크므로 mid를 줄이기 위해 end = mid - 1 / 반대로 (2) mid 5라면 수용 가능 인원보다 M명이 작으므로 mid를 키우기 위해 start = mid + 1 진행

---