[BOJ] 용액 합성하기(14921) - 그래프

문제 url: https://www.acmicpc.net/problem/14921

난이도: Gold5

정답률:

권장 시간: 분

권장 시간 복잡도:

분류: 투 포인터, 이분 탐색

 

문제 설명

홍익대학교 화학연구소에서는 산성과 알칼리성 용액을 혼합하여 특수한 성질을 가진 용액을 만들려고 한다.
산성 용액의 특성값은 음의 정수로 나타나고, 알칼리성 용액의 특성값은 양의 정수로 나타난다.

같은 양의 두 용액을 혼합하면, 두 특성값의 합으로 특성값이 정의된다.
이 연구소에서는 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

예를 들어, 서로 다른 용액의 특성값이

-2, 4, -99, -1, 98

이라면, 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액은 -99와 98을 혼합한 -1이다.

입력으로 주어진 용액의 특성값은 모두 다르다고 가정하며, 산성 용액과 알칼리성 용액 중 하나씩만 혼합하여야 한다.

---

입력

첫째 줄에 용액의 수 N이 주어진다.
(2 ≤ N ≤ 100,000)

둘째 줄에는 각 용액의 특성값이 공백으로 구분되어 주어진다.
특성값은 절댓값이 1,000,000,000을 넘지 않는 정수이며, 모두 다르다.

---

출력

첫째 줄에 두 용액을 혼합하여 만들 수 있는 특성값 중
0에 가장 가까운 값을 출력한다.

---

예제 입력 1

5  
-2 4 -99 -1 98  

---

예제 출력 1

-1  

 

내 풀이

n = int(input())
li = list(map(int,input().split()))

start = 0
end = len(li)-1

min = float("inf")
while start < end:
  sum = li[start] + li[end]
  if abs(sum) < abs(min):
    min = sum
  if sum < 0:
    start += 1
  else:
    end -= 1
print(min)