[2470] 두 용액

문제

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

문제풀이 kick

[기존 이분탐색] arr에서 value 찾기
[문제] arr에 '쌍이 되는' target 찾기

코드

import sys

n=int(input())
li=list(map(int,input().split()))
li.sort()

def find_pair_value(left, right, value):
    optimalPairValue=0
    optimalPairTotal=sys.maxsize

    while left<=right:
        mid=(left+right)//2
        sum=value+li[mid]

		# 최적값 갱신 
        if abs(sum)<optimalPairTotal:
            optimalPairValue=li[mid]
            optimalPairTotal=abs(sum)

        if sum<0:
            left=mid+1
        elif sum>0:
            right=mid-1
        else:
            return li[mid]
            # 찾으면 그냥 반환 
    return optimalPairValue

ans1,ans2=0,0
ans_total=sys.maxsize

for i in range(0,n-1):
	# 리스트는 정렬되어 있음.
    # i>j 일때,arr[j]는 arr[j]보다 작은 값이기 때문에 더해서 0을 만들 수 있는 최적의 해가 아님. 따라서 i+1 부터 탐색.
    pair_value=find_pair_value(i+1, n-1, li[i])
    total=abs(li[i]+pair_value)
    # 정답 갱신 
    if total<ans_total:
        ans_total=total
        ans1, ans2= li[i], pair_value
print(ans1, ans2)