BOJ 2473 | 세 용액

간단한 이분탐색 문제인데 한참 헤맸다.

난 정렬한 수열에서 양 끝 점을 잡고 투 포인터로 점점 좁혀나가면서 그리디를 수행했는데, 계속 WA가 나와서 아이디어에 문제가 있다는 걸 알았다.

뭔가 어떤 case에서 정답을 놓치는 일이 발생하는 것 같은데, 그게 어딘지 모르겠어서 그냥 $O(N^2)$으로 왼쪽부터 p1 p2를 두면서 완전탐색하고 p3는 p2~N까지 이분탐색했다.

p1+p2+p3가 0에 가까워야 하므로 당연히 이분탐색으로 p3를 구할 수 있다.

[... p1 p2 p3] 까지 탐색하면 모든 구간을 탐색했기 때문에 WA가 날 일은 없다. 근데 파이썬으로 풀어서 pypy로 제출 안하면 TLE난다.

코드

def lower_bound(nums, lo, target):
    hi = len(nums)-1
    while lo + 1 < hi:
        mid = int((lo+hi)/2)
        if (nums[mid] <= target): lo = mid
        else: hi = mid
    if (abs(target - nums[lo]) < abs(target - nums[hi])):
        return nums[lo]
    else : return nums[hi]

N = int(input())
arr = list(map(int, input().split()))
arr.sort()

ans = [0, 0, 0]
asv = 5000000000

for xp in range(0, N-2):
    for yp in range(xp+1, N-1):
        t = arr[xp] + arr[yp]
        idx3v = lower_bound(arr, yp+1, t*-1)
        if ( abs(t + idx3v) < abs(asv) ):
            ans = [arr[xp], arr[yp], idx3v]
            asv = t + idx3v

ans.sort()
print(ans[0], ans[1], ans[2])