[#알고리즘/이진 탐색/[백준]2470번:두 용액(python)]

Question

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

Solution

1. 용액의 특성값을 list로 입력 받아 오름차순 정렬을 한다.
2. 기준값(answer)을 처음 start 위치의 값과 end 위치의 값의 합으로 설정한다.
3. start = end일 때까지 total이 0보다 크면 end를 -1하고, 0보다 작으면 start를 +1 한다.
4. end 혹은 start를 옮길 때마다 새로운 total을 구해 기존의 기준값보다 작으면 해당 값을 기준값으로 설정한다. 이때, 기준값보다 작은 경우일 때의 start와 end를 계속 갱신한다.
5. 결국 두 용액의 합이 가장 작은 경우일 때의 start와 end를 구할 수 있게 된다. 이때의 start와 end 위치의 두 값이 답이 된다.

Code

import sys

n = int(input())
solution = list(map(int, sys.stdin.readline().split()))
solution.sort()

start = 0
end = n - 1
answer = abs(solution[start] + solution[end])

s_start = start
s_end = end

while(start < end) :
    total = 0
    total = solution[start] + solution[end]
    
    if abs(total) < answer :
        answer = abs(total)
        s_start = start
        s_end = end
        if answer == 0 :
            break
    if total > 0 :
        end -= 1
    else :
        start += 1

print(solution[s_start], solution[s_end])

후기

값을 비교하면서 탐색을 해야하는 경우는 기준값을 설정하자 .... ( ╯□╰ )
여기선 새로운 두 원소 조합의 합이 기존의 어떠한 값과 비교했을 때 작은 지를 비교한다.