[Baekjoon] 2467 용액

문제

두 개 더해서 0에 가장 가까운 값을 구해라.

 

문제 원본

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

 

풀이

1. 두 값 중에 작은 값을 정해가면서 비교한다.

2. 작은 값 이상의 값들에서 이진 탐색으로 두 합이 0에 가장 가까워지는 값을 찾는다.

import sys
input = sys.stdin.readline

n = int(input())
liquids = list(map(int, input().split()))

answer = float("INF")
left = 0
right = 0

for i in range(n-1):
    now = liquids[i]
    s, e = i+1, n-1

    while s <= e:
        mid = (s+e) // 2
        tmp = now + liquids[mid]

        if abs(tmp) < answer:
            answer = abs(tmp)
            left = i
            right = mid

            if tmp == 0:
                break
        
        if tmp < 0:
            s = mid + 1
        else:
            e= mid - 1

print(liquids[left], liquids[right])