[Binary Search] BOJ 2470 두 용액

🎈 백준 2470 두 용액

www.acmicpc.net/problem/2470

2470번: 두 용액

 

❗ 문제의 핵심, 풀이 과정

•  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

=> 범위를 생각하면 완전탐색으로 풀 수 없다.

 

• 산성 용액(양의 정수 값), 알칼리성 용액(음의 정수 값) 중 두 용액을 혼합한다.

=> 같은 종류도 혼합할 수 있다.

 

• 두 용액의 혼합한 특성값이 0에 가장 가까운 값을 가질 때의 두 용액을 찾아야 한다.

=> 한 용액을 기준으로 이 용액을 제외한 나머지 용액과의 특성값의 합이 0과 가장 가까운 것을 찾는다. (이진탐색 이용)

     - 정렬된 용액 정렬 arr에서 for를 이용하여 i번째 용액을 기준으로 설정한다.

     - 혼합 특성값이 0과 가까운 나머지 용액을 찾기 위해 start = i + 1, end - n - 1로 설정한다.

     - 가장 0과 가까운 혼합 특성값을 찾기 위해 min_s를 설정하여 절댓값이 작은 혼합 특성값을 저장하고, 그 때의 용액을 저장한다.

     - 혼합 특성값이 0보다 작으면 더 큰 값을 더해주어야 하고, 0보다 크면 더 작은 값을 더해주어야 한다.

 

✅ 전체 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort()  # 정렬
min_s= 2000000001

if n == 2:
    print(arr[0], arr[1])
    exit(0)

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

    # [i+1, n-1] 의 값 + i번째 값의 합을 비교해나간다.
    while start <= end:
        mid = (start + end) // 2
        s = arr[i] + arr[mid]

        # 혼합 특성값이 0에 가까운 용액을 저장한다.
        if abs(s) < min_s:
            idx1, idx2, min_s = i, mid, abs(s)

        # 혼합 특성값이 0보다 작다면 더 큰 값을 더해주어야 한다.
        if s < 0:
            start = mid + 1
        # 혼합 특성값이 0보다 크다면 더 작은 값을 더해주어야 한다.
        else:
            end = mid - 1

print(arr[idx1], arr[idx2])

# 투포인터x, 이분탐색으로 풀었을 때