백준 2467 용액 Python

🐸 문제 정보

2467번: 용액

 

🤖 알고리즘

이진탐색

 

⏱️ 풀이 시간

19.00m

 

📝 풀이

1. 용액의 점수는 오름차순으로 입력된다.
2. 때문에 start는 0, end는 n-1 인덱스로 잡고 시작한다.
3. 두 점수의 합이 최소값이 되는 순간까지 이진탐색을 실행한다.
4. 만약 두 점수의 합이 0이라면, 이보다 작을 수는 없기 때문에 거기서 멈춘다.

이분탐색은 계속 풀어도 뭔가 붕뜨게 이해되는 느낌이다... 더 더 많이 풀어봐야 할 것 같다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
scores = list(map(int, input().rstrip().split()))
gap = sys.maxsize
res = (0, 0)

start = 0
end = n - 1
while start < end:
    cur = scores[start] + scores[end]
    if abs(cur) < gap:
        gap = abs(cur)
        res = (scores[start], scores[end])
    if cur == 0:
        break
    elif cur > 0:
        end -= 1
    elif cur < 0:
        start += 1

print(*res)