[백준] 2473. 세 용액 - Python

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

2473번: 세 용액

---

• 풀이
  • 조합
    • N이 최대 5000이므로 조합 사용시 시간 초과 발생
  • 3개를 선택해야하는데 고정값이 있으면 편할 듯
    • 2개를 고정하고 최적의 1개 찾기
      • 시간 초과
    • 1개를 고정하고 최적의 2개 찾기(투 포인트)
      • 이분탐색
      • 합이 0이면 멈추기
        • sys.exit()

-97 고정

-97

-6

-2

2

6

98

-6과 98 선택 ->  숫자의 합 : -5 -> 음수이므로 오른쪽으로 한 칸 이동

-97

-6

-2

2

6

98

-2과 98 선택 -> 숫자의 합 : -1 -> 음수이므로 오른쪽으로 한 칸 이동

-97

-6

-2

2

6

98

2와 98 선택 -> 숫자의 합 : 3 -> 양수이므로 왼쪽으로 한 칸 이동

-97

-6

-2

2

6

98

2와 6 선택 -> 숫자의 합 : -89 -> 음수이므로 오른쪽으로 한 칸 이동

# 고정 값 이동!!

• 코드

import sys
input = sys.stdin.readline

# 용액의 수
N = int(input())

feature = list(map(int, input().split()))
feature.sort()

result = []
# 중복 가능 [10억,10억,10억,10억] 인경우
min_sum = 4000000000

for one in range(N-2):
    two = one+1
    three = N-1
    while two < three:
        c_sum = feature[one] + feature[two] + feature[three]
        # 0에 더 가까우면 갱신
        if abs(c_sum) < abs(min_sum):
            min_sum = c_sum
            result = [feature[one],feature[two],feature[three]]
            
        # 특성값이 0이면 끝내기
        if c_sum == 0:
            print(*result)
            sys.exit()
       
        # 0보다 작으면 two 값 늘리기
        if c_sum < 0:
            two += 1
        # 0보다 크면 three 값 줄이기
        elif c_sum > 0:
            three -= 1
        
print(*result)