백준_2467_용액

문제

2467번: 용액

풀이

1. 구해야 하는 두 수 중 첫번째 수 a를 선택한다.

2. 지정한 수보다 오른쪽에 있는 수들을 탐색 범위[startPoint, endPoint]로 지정한다.

3. 이분 탐색을 통해 첫번째 수 a와의 합이 0에 가장 가까운 두번째 수 b를 찾는다.

• 3-1. a+startPoint와 a+endPoint의 곱의 부호가 -이라면 startPoint는 startPoint와 endPoint의 중간이 된다.
• 3-2. a+startPoint와 a+endPoint의 곱의 부호가 +이거나 곱이 0이라면 탐색을 중단한다.

4. a+startPoint와 a+endPoint 중 작은 값을 기록한다.

코드

N = int(input())
arr = list(map(int, input().split()))

num = abs(sum(arr[-2:])) # arr의 뒤에서 두자리 수를 선택
ans = arr[-2:] # arr의 뒤에서 두자리 수를 선택

for i in range(N-1) :
    s, e = i+1, N-1
    while e-s>1 :
        n1 = arr[s]+arr[i]
        n2 = arr[e]+arr[i]
        
        if n1*n2<0 :
            p = int((s+e)/2) # s와 e의 중간 지점
            n3 = arr[p]+arr[i]
            
            if n2*n3<=0 : s = p
            else : e = p
            
        # n1과 n2의 부호가 같거나 0이 두 수에 포함될 때
        else: break
	
    # 시작점과 끝점만 탐색
    for j in [s, e] :
        tmp = abs(arr[i]+arr[j])
        if num>tmp : num, ans = tmp, [arr[i], arr[j]]
print(*ans)