[백준][2470] 두 용액

• Problem Link : https://www.acmicpc.net/problem/2470

문제

• N개의 용액의 특성 값이 주어진다.
• 특성 값의 합이 0에 가장 가깝게 되는 두 용액의 특성 값을 구해라

입력

• 첫째 줄, 용액의 수 N이 주어진다.
• 둘째 줄, N개의 용액의 특성 값이 공백을 사이에 두고 주어진다.

출력

• 특성 값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다.

풀이

가장 작은 수(음수)와 가장 큰 수(양수)부터 더하기 시작해서 모든 용액의 특성값 합이 최소가 되는 경우의 특성 값을 계속 업데이트하면서 반복문이 끝났을때 해당 값을 출력한다. 이 때 오름 차순으로 정렬해준 후 left index와 right index로 양 끝점에서부터 접근하면 자연스럽게 가장 작은 수와 가장 큰 수부터 더해주면서 특성 값의 합을 확인할 수 있다. 계산한 특성값이 초기값으로 주어진 특성 값 합보다 작을 경우 해당 특성의 값을 저장해준다. 그 후 index의 이동 과정이 중요한데 다음과 같이 두 가지 경우가 있을 수 있다.

• 특성 값의 합 < 0
  음수의 값이 너무 작아서 합이 음수로 나온다. 따라서 0에 가까워지기 위해서는 작은 수를 조금 작은 수로 바꿔줄 필요가 있다. 따라서 left index를 +1 해준다.

• 특성 값의 합 > 0
  음수의 값이 너무 작아서 합이 양수로 나온다. 따라서 0에 가까워지기 위해서는 큰 수를 조금 큰 수로 바꿔줄 필요가 있다. 따라서 rigt index를 -1 해준다.

첫번째 경우에서는 right index +1 해주고 두번째 경우에는 left index를 -1 해줘도 합이 0에 더 가까워지지 않나요?

• 시작을 양 끝점, 가장 작은 수와 가장 큰 수로 시작했기 때문에 left index의 진행방향이 오른쪽으로 고정되며, right index의 진행방향 또한 왼쪽으로 고정된다.

• 위 그림을 보면 두 특성 값의 합이 음수일 경우에는 left를, 두 특성 값의 합이 양수일 경우에는 right를 움직이는데 이는 sum을 0에 가깝게 만들기 위해서 음수일 경우 음수의 크기를 더 작게, 양수일 경우 양수의 크기를 더 작게 만드는 과정을 반복하는 과정이다.
• 이를 잘 보면 한 쪽 index를 고정시킨 후 특성의 합이 최소가 되도록 반대쪽 index를 조정하는 방식의 반복이라고 볼 수 있다. 실제로 left를 고정해두었다고 가정해보면 첫 left가 -99일때 자신과 특성의 합이 0에 가까운 60과 마지막으로 sum을 구했고 두 번째 left가 -18일때 right가 계속 움직이며 left와 while문이 끝나기 전 마지막으로 신과 특성의 합이 0에 가까운 21과 sum을 구했다는 것을 볼 수 있다.

결론적으로 모든 값에서 합이 0에 가까워지는 최적의 상대를 찾는다.

코드

import sys

input = sys.stdin.readline

n = int(input())
solution = list(map(int, input().split()))
solution.sort()

left = 0
right = n - 1

min_gap = abs(solution[left] + solution[right])
ans = [solution[left], solution[right]]

while left < right:
    sum = solution[left] + solution[right]
    if abs(sum) < min_gap:
        min_gap = abs(sum)
        ans = [solution[left], solution[right]]
        if ans == 0:
            break
    if sum < 0:
        left += 1
    else:
        right -= 1

print(ans[0], ans[1])