2470 두 용액

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys

read =sys.stdin.readline
N = int(input())
val_list = list(map(int,read().split()))
val_list.sort()

start = 0
end = N-1
min_val = 1e12

answer = []
while (start<end):
    sum_ = val_list[start]+val_list[end]

    if min_val > abs(sum_):
        min_val = abs(sum_)
        answer = [val_list[start],val_list[end]]
    if sum_ < 0:
        start += 1
    else:
        end -=1

print(answer[0],answer[1])

3. 문제 풀이

와.. 이것도 결국 못풀었는데 이진탐색의 새로운 유형이다. 이걸 이렇게도 활용하는가 싶다. 항상 어떤 mid값의 위치를 이용하는 문제를 풀었는데, 이것은 양 끝단을 점점 좁혀오는 문제이다. 아예 유형이 달라서 어떻게 해야할지 난감했다ㅠ 알고리즘 자체는 쉬운편이므로 자주 봐서 익히자.

두 끝단을 천천히 좁혀오면서 그때마다 둘의 차이를 계산한다. 그 차이 값이 기존의 최소값보다 작게되면 정답으로 갱신한다. 무한 루프를 돌고 있으므로, 차이 값의 부호에 따라 좌우 끝단의 위치를 계속 좁혀온다. 그러다가 무한 루프의 조건문을 깨거나, 차이가 0이 되었을 경우 이를 반환한다.