BOJ 2470번: 두 용액

www.acmicpc.net/problem/2470

2470번: 두 용액

아이디어:

이분 탐색으로 푼다는 게 무조건 mid 값을 찾는다는 게 아닌가보다..((아닐수도))

1. 정렬

2. high = n-1, low = 0으로 포인터를 설정하고, while문을 수행하면서 특성값을 구하고 절댓값을 취하여 최솟값을 업데이트한다. 특성값이 음수면 low++(0에 가까워지려면 커져야 되니까), 양수면 high--(0에 가까워지려면 작아져야 되니까)

 

import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort() #오름차순 정렬

high = n-1
low = 0
ans = 2000000000

while (high>low): 
    value = arr[high]+arr[low] #특성값 계산
    if (abs(ans)>abs(value)):
        ans = value
        left = low
        right = high
    if (value<0): #특성값이 음수인 경우에는 0에 가까워지려면 커져야 함.
        low+=1 
    elif (value>0): #특성값이 양수인 경우에는 0에 가까워지려면 작아져야 함.
        high-=1
    else: #특성값이 0이면 바로 출력
        break
print(arr[left], arr[right])

※ ans를 설정하는 부분에서 오류가 있었다. 그냥 맘 편하게 최댓값으로 설정하자.

※ while문에서 이전의 이분탐색에서는 high>=low 였는데, 이 문제의 경우는 그렇게 설정하면 같은 값을 두 번 더하게 될 수 있기 때문에 조건식을 high>low로 해야 한다.