[BOJ] 2473번 - 세 용액

[BOJ] 2473번 - 세 용액 

 

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

2473번: 세 용액

 

알고리즘

---

각 용액의 3가지의 합이 최소가 되는 경우의 수를 찾아야한다.

이분탐색을 이용하여 하나를 선택한 다음에 나머지 두가지를 매칭하는 방법을 사용하였다.

1. 데이터를 입력 받는다.

2. 이분 탐색을 위하여 데이터를 정렬한다.

3. 각 용액 별로 최소의 경우(left , right 를 두어 결과 값이 0보다 크면 right를 작게 반대는 left를 크게)를 이분 탐색으로 찾아 해당되면 갱신

4. 모든 경우의 수 중 가장 작은 결과를 출력

 

코드

---

#BOJ 2473번

import sys
input = sys.stdin.readline

n = int(input())
datas = list(map(int,input().split()))
datas.sort()
answer = []
current = 3000000001

for i in range(n) :
    temp = datas[:i]+datas[i+1:]
    start , end = 0 , n-2
    while start < end :
        target = datas[i]+temp[start]+temp[end]
        if current > abs(target) :
            answer = [datas[i],temp[start],temp[end]]
            current = abs(target)

        if target > 0 :
            end -= 1
        else :
            start += 1

answer.sort()
print(*answer)