[파이썬] 백준 2473 : 세 용액 (골드3)

[파이썬] 백준 2473 : 세 용액 (골드3)

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

---

풀이

방향성 생각

• 정렬 이후 두 용액의 구한 후, 나머지 하나를 이분탐색으로 빠르게 찾기
• or 한 피벗의 값을 정해놓고 투포인터 진행
  • 정렬이 되어있는 array에서 값을 늘리거나 줄이거나만 해야하므로 피벗, 피벗+1, 맨 끝을 정한다.
  • l = pivot+1, r=맨끝 이렇게 정한 후 용액의 ph값에 따라서 l r 움직이기.
• 후자로 풀이 진행

 

---

전체코드

import sys

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

temp = sys.maxsize
answer = []
for p in range(N-2):
    l,r = p+1,N-1

    while l < r:
        idx = [p,l,r]
        ph = sum(arr[i] for i in idx)
        if abs(ph) < abs(temp):
            temp = ph
            answer = [arr[i] for i in idx]

        if ph < 0:
            l += 1
        elif ph > 0:
            r -= 1
        else:
            answer = [arr[i] for i in idx]
            break

answer.sort()
print(*answer)

코멘트

• .