[python] 백준 2473 세 용액

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

2473번: 세 용액

 

문제 해결

• 전형적인 이분탐색 문제 (세 원소의 합이 C(상수) 일때 세 원소를 구하는 문제)
• 가장 작은 수를 고정시키고 나머지 두 수를 이분탐색으로 구하는 문제
• 그런데 python3에서는 시간초과가 난다...ㅜㅜ(pypy3에서는 잘 풀림) 근데 다른 분들도 이렇게 많이 푼듯?

 

CODE

import sys
input = sys.stdin.readline
INF =sys.maxsize
n = int(input())
A = list(map(int, input().split()))
A.sort()
target = INF
answer = [-1,-1,-1]
for i in range(n-2):
    start = i+1
    end = n-1
    while start<end:
        if abs(A[i]+A[start]+A[end]) < abs(target):
            target = A[i] + A[start] + A[end]
            answer[0], answer[1], answer[2] = A[i], A[start], A[end]
        if A[i]+A[start]+A[end] >0:
            end -= 1
        elif A[i]+A[start]+A[end] <0:
            start += 1
        elif A[i]+A[start]+A[end] ==0:break
print(*answer)

 

유사문제

https://thought-process-ing.tistory.com/252

[python] 백준 3151 합이 0