백준 2473번 : 세 용액

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

2473번: 세 용액

 

전형적인 투 포인터 알고리즘 문제를 조금 복잡하게 꼬아낸 문제이다.

 

서로 다른 값을 가진 N개 (3 <= N <= 5000)의 용액이 존재하는데, 이 N개의 용액에서 3개의 용액을 합했을때 그 값을 가장 0에 가깝게 만들 수 있는 용액의 조합을 찾는 문제이다. 

 

언제나 그렇듯 완전탐색으로 N개의 용액 중에서 순서와 상관없이 3개를 선택하는 조합을 모두 구하는 방법이 있으나, 그렇게 하면 O(N^3) 시간 복잡도를 가지므로 시간초과 판정을 받는다. 따라서 다른 방법을 생각해야했다.

 

만약 3개가 아니라 2개의 용액을 합하는 문제라고 생각해보자. 먼저 모든 용액의 값을 오름차순 정렬하고 포인터가 양 끝 용액(왼쪽: 0, 오른쪽: N-1)을 가리키도록 한다. 이때 포인터가 가리키는 용액은 N개의 용액들 중에서 가장 작은 값과 큰 값을 가지는 용액이다.

 

만약 포인터가 가리키는 두 용액을 더한 값이 양수라면 값을 낮춰서 0에 가깝게 만들어야하고, 음수라면 값을 높여서 0에 가깝게 만들어줘야한다. 오른쪽 포인터를 왼쪽으로 옮길수록 두 용액을 합한 값은 작아지고 왼쪽 포인터를 오른쪽으로 옮길수록 값이 커지는 성향을 이용한다.

 

값으로 정렬된 N개의 용액을 순서대로 확인하면서 투 포인터를 적용한다. i번째 용액을 선택했다고 가정하면, 양 끝 포인터를 i+1번과 N-1번 인덱스로 설정하고 세 용액 (i번째 용액 + 두 포인터가 가리키는 용액)의 합이 가장 0에 가까운 값을 찾아낼 수 있다. 즉, i번째 용액을 반드시 포함시켰을때의 경우들 중에서 최적값(0에 가까운 값)을 찾고, 찾은 N개의 값들 중에서 절댓값이 가장 작은 값이 문제에서 요구하는 정답이 된다.

 

핵심적인 문제 해결 아이디어는 N개의 각 용액마다 그 용액을 반드시 포함(혼합)한다고 가정한 상태에서 투 포인터 알고리즘을 적용시키는 것이다. 이 방법으로 O(N^2)의 시간 복잡도로 문제를 해결할 수 있다.

import sys
input = sys.stdin.readline

n = int(input())
d = sorted(list(map(int, input().split())))
m = 3*(10**9)
r = []

for i in range(n-2):
    s, e = i+1, n-1
    while s < e:
        v = d[i] + d[s] + d[e]
        if m > abs(v):
            m = abs(v)
            r = [d[i], d[s], d[e]]

        if v > 0:
            e -= 1
        elif v == 0:
            print(d[i], d[s], d[e])
            exit()
        else:
            s += 1
print(*r, sep=' ')