백준 GOLD 5 [2470번] 두 용액 Python

문제 링크

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

2470번: 두 용액

정답 코드

import sys
input = sys.stdin.readline
N = int(input())
SOLUTIONS = sorted(list(map(int, input().split())))
answer = []
twoSum = 2000000001
isFound = False
for i in range(N):
    # 처음 부터 시작
    startSolution = SOLUTIONS[i]
    start = i + 1
    end = N - 1
    while end >= start:
        middle = (start + end) // 2
        currentSolution = SOLUTIONS[middle]
        currentSum = currentSolution + startSolution
        if currentSum == 0:
            answer = [startSolution, currentSolution]
            isFound = True
            break
        elif currentSum > 0:
            end = middle - 1
        else:
            start = middle + 1

        if abs(currentSum) < twoSum:
            twoSum = abs(currentSum)
            answer = [startSolution, currentSolution]

    if isFound:
        break
print(*answer)

풀이 방법

- 특정 값에 가까운 값을 찾는 거 하면 바로 이분탐색이 떠올라야 한다.

- 정렬을 해주는 것은 기본 중의 기본

- 맨 왼쪽 값을 뽑고 이제 나머지 값을 찾는다.

- 나머지 값을 하나의 리스트로 보고 맨 왼쪽을 start, 맨 오른쪽을 end index로 놓는다.

- middle index의 용액과 현재 뽑아 놓은 용액을 더했을 때 0보다 크면 middle 이후의 값을 더해봤자 0보다 크기 때문에 end값을 middle - 1로 바꾼다.

    - 이 부분에서 틀리는 점이 이미 계산한 값을 버려야 하는데 까먹고 end = middle로 한다거나 습관적으로 end = middle + 1을 한다거나 하면 틀릴 수밖에 없다.

- 더했을 때 0보다 작다는 말은 middle 이전의 값을 더해봤자 0보다 작기 때문에 end값을 middle + 1로 바꾼다.

- 구간별로 두 용액을 더해서 그 합이 최소 값이 될 수 있도록 검사한다.

느낀점

- 단순 이분 탐색이지만 이분 탐색 문제를 많이 접해보지 못했기 때문에 오래 걸릴 번 했던 문제다.

- 이분 탐색을 할 때 가장 먼저 알아야 할 부분이 start, end, middle을 어떻게 설정할 것인지이다.

- 많은 경험을 통해서 이해하는 방법밖에 없으며 무작정 외운다고 해서 풀 수 있는 알고리즘은 아니다.