[백준] 2473. 세 용액 - 파이썬

[Gold III]

 

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

2473번: 세 용액

 

풀이

[백준] 2467. 용액 - 파이썬 의 업그레이드(?) 버전.

2467번 용액 문제는 N <= 100,000 이였지만,

2473번 세 용액 문제는 3개인 만큼 N <= 5,000인 것을 볼 수 있다.

그렇다고 해서, 2467번처럼 단순하게 모든 2개의 쌍에 대한 나머지 1개를 이진 탐색으로 구하는 방식으로 접근한다면, O(N^2 logN)이 되어.. TLE가 날 것이라고 생각. (5000^2 만 해도 2500만개 * log(5000). 2467번 용액 문제만 해도 O(N logN)으로 접근하면 약 160만개였고, 100배 이상 차이가 남.)

그렇다면, Binary Search로는 답이 안 나오므로, 2467번의 Binary Search에서 풀이했던 느낌으로,

N개의 용액 각각에 대해 다른 두 개의 용액을 Two Pointer로 구하는 방식으로 생각해 보았다.

A, B, C, D, E, F, G 용액이 있다면, A용액과 함께 특성값을 0에 가깝게 만들 수 있는 두 용액을 B~G 중에서 Two Pointer를 이용해 2개 선택.

마찬가지로 B용액과 함께 특성값을 0에 가깝게 만들 수 있는 두 용액을 C~G 중에서 Two Pointer로 2개 선택.

...

 

N = int(input())
sol = list(map(int, input().split()))
sol.sort()
 
result = [1000000000, 1000000000, 1000000000]
for k in range(N):
    i = k+1
    j = N-1
    while i < j:
        if abs(sol[i]+sol[j]+sol[k]) < abs(sum(result)):
            result = [sol[k], sol[i], sol[j]]
 
        if sol[i]+sol[j]+sol[k] > 0:
            j -= 1
        elif sol[i]+sol[j]+sol[k] < 0:
            i += 1
        else:
            break
 
print(*result)