🧪 백준 2470번 : 두 용액

📝 문제

🔗 Link - BOJ 2470번 두 용액

💡 풀이

이진 탐색을 이용했다. 2467번 용액 문제는 입력이 오름차순 정렬이 이루어진 상태에서 주어지지만, 이 문제는 정렬된 상태에서 주어지지 않는다. 그러므로 이진탐색을 하기 위해 정렬을 먼저 수행해야 한다.

용액의 처음부터 끝까지 돌면서 합의 절댓값이 가장 작을 때의 용액을 찾아주면 된다.

주의해야 할 점
용액의 초기값 설정
result = 2*int(1e9)+1

result(용액의 합) 초기값 잘 설정해주어야 한다. 이거 때문에 계속 NameError가 났다..

단순히 int(1e9)로 하면 안되는 이유는 문제에서 1,000,000,000이 최댓값이기 때문에 용액 2개를 합하면 2,000,000,000이 된다. 작은 값을 찾아야 하는데 용액의 합보다 더 작은 값이 초기값으로 들어오게 되면 이진탐색 수행이 제대로 이루어지지 않는다.

if temp < 0:
	start = mid+1
else:
	end = mid-1

이진 탐색은 위와 같이 temp(용액의 합)이 음수라면 start값을 mid+1로 조정하여 양수의 값을 더하도록 하고 temp가 양수라면 end값을 mid-1로 조정하여 음수의 값을 더하도록 한다.

💻 소스코드

# 2470 : 두 용액

import sys
input = sys.stdin.readline

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

sol.sort()
result = 2*int(1e9)+1

for i in range(N-1):
    start, end = i+1, N-1

    while start <= end:
        mid = (start+end) // 2
        temp = sol[i]+sol[mid]

        if abs(temp) < result:
            result = abs(temp)
            sol1, sol2 = i, mid

        if temp < 0:
            start = mid+1

        else:
            end = mid-1

print(sol[sol1], sol[sol2])