[이진 탐색] 백준 2473번: 세 용액 / 골드 4

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

2473번: 세 용액

import sys
input = sys.stdin.readline
n = int(input())
lst = list(map(int, input().split()))
lst.sort()

if lst[-1]<0: # all elem is negative
    print(lst[-3], lst[-2], lst[-1])
    quit()
if lst[0]>0: # all elem is positive
    print(lst[0], lst[1], lst[2])
    quit()


def bsearch(target, i):
    left = i + 1
    right = len(lst) - 1
    while left <= right:
        mid = (left + right)//2
        if lst[mid] < target:
            left = mid + 1
        elif lst[mid] > target:
            right = mid - 1
        else:
            return mid

    a = abs(target - lst[mid])
    b = abs(target - lst[mid-1])

    if i+1 == mid:
        return mid

    if a < b:
        return mid
    else:
        return mid - 1

diff = sys.maxsize
answer = []
for i in range(n-2):
    for j in range(i+1, n-1):
        target = -(lst[i]+lst[j])
        idx = bsearch(target, j)
        if abs(target - lst[idx]) < diff:
            answer = [lst[i], lst[j], lst[idx]]
            diff = abs(target - lst[idx])

print(*answer)

 

첫번째 두번째 원소는 반복문을 돌고 마지막 원소만 이진 탐색으로 탐색하는 방법으로 했더니

정말 아슬아슬하게 통과했다.

 

통과자들의 코드를 보니 첫번째 원소로만 반복문을 돌리고 두번째, 세번째 원소를 각각 투포인터로 조절하였다.

합계가 0보다 크다 -> right를 줄이기

합계가 0보다 작다 -> left를 올리기

왜 이 생각을 못했을까.