[BOJ/2473] 세 용액

문제 링크

문제 링크

문제 풀이

‘세 용액’ 문제는 ‘용액’ 문제의 심화 문제이다. 용액 문제 링크

‘용액’ 문제는 두 개의 용액을 선택하여, 두 용액의 값의 합이 0에 가장 가까운 경우의 조합을 구하는 문제이다.
‘세 용액’ 문제를 풀기 전에 ‘용액’ 문제의 풀이를 먼저 한 뒤 ‘세 용액’ 문제의 풀이를 해보겠다.

'용액' 문제 풀이

용액을 오름차순으로 정렬하고, 그 중 가장 값이 작은 용액을 A[i]로 칭하고 가장 값이 큰 용액을 A[j]라고 하자.

그 둘의 합이 양수인 경우를 생각해보자.
문제의 최적해는 용액의 합이 0에 가장 가까운 경우의 해이기 때문에 A[i]가 아닌 A[i+k]를 A[j]와 더하면 그 값이 더 커지기 때문에 최적해를 절대 찾을 수 없게 된다.

반대로, 둘의 합이 음수인 경우를 생각해보자.
A[j]가 아닌 A[j-k]를 A[i]와 더하면 그 값이 더 작아지기 때문에 최적해를 절대 찾을 수 없게 된다.

따라서, A[i]와 A[j]의 합에 따라 i, j의 값을 조절해가며 최적해를 탐색하면 된다.

---

‘세 용액’ 문제는 세 용액을 하나 선택한 뒤, ‘용액’ 문제를 풀었던 것 처럼 최적해를 찾아나가면서 풀이하면 된다.

A[0]가 세 용액 중 하나인 경우의 최적해를 탐색하고 A[1]가 세 용액 중 하나인 경우의 최적해를 탐색하고, … 그렇게 탐색해나가다 보면 전역적인 최적해를 구할 수 있다!

코드

import sys
input = sys.stdin.readline

n = int(input())
li = sorted(list(map(int, input().split())))
ans = [li[0], li[1], li[2]]
minVal = sys.maxsize

for fixed in range(0, n-2):
    # 숫자 하나를 고정시키고 투포인터를 사용해 정답 찾기
    left, right = fixed + 1, n-1

    while left != right:
        summation = li[fixed] + li[left] + li[right]
        # 세 용액의 합이 정답인지 확인 및 갱신
        if minVal > abs(summation):
            minVal = abs(summation)
            ans = [li[fixed], li[left], li[right]]

        # 세 용액을 더한 값이 양수라면: 오른쪽을 왼쪽으로 당김
        if summation > 0:
            right -= 1
        # 세 용액을 더한 값이 음수라면: 왼쪽을 오른쪽으로 밂
        elif summation < 0:
            left += 1
        else: break

print(' '.join(map(str, ans)))