[백준] 2467 - 용액

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

2467번: 용액

 

문제 한줄 이해

- 용액의 특성을 나타내는 정수가 주어졌을 때 용액들을 섞어 최대한 0의 가까운 경우를 구하기

생각난 풀이

문제를 읽고 생각난 필요한 조건들

1. 먼저 문제에서 입력이 정렬된 상태에서 들어온다, n의 값이 크다 -> 투포인터, 이분탐색을 예상해볼 수 있다.

2. 값들 중 2개를 골라 모든 경우의 수를 파악해 제일 작은 경우를 구하면 되지만 시간 복잡도에서 문제가 생긴다

-> 그렇다면 투포인터를 활용해 탐색

-> 투포인터는 항상 어떻게 기준을 삼을 것인지 파악이 중요

-> 그렇다면 예를 들어서 파악하기

-5 -4 -3 -2 -1 0 6 7 8 9 10이 있다고 치자

이때 시작위치를 처음(left)과 끝위치(n-1)로 지정을 해보자

우리가 원하는건 0에 가깝게인데 -5와 10을 더하면 5인데 0에 더 가깝게 하려면 끝위치를 한단계 앞으로 댕기면 10보다는 작은 수가 선택이 되면서 점점 0에 가까워 질 수 있다.

따라서 두개의 값을 더했을 때 0보다 큰 경우에는 끝에 위치를 댕겨 덜 큰 값을 더해주고

                                            0보다 작은 경우는 앞으로 댕기면서 덜 작은 값을 더해주면 된다.

 

import sys
n = int(sys.stdin.readline())
nlist = list(map(int,sys.stdin.readline().split()))
left = 0
right = n-1
result = abs(nlist[left] + nlist[right])
a = nlist[left]
b = nlist[right]

while left < right:
	//0에 가깝다는 것은 절대 값
    if abs(nlist[left] + nlist[right]) < result:
        result = abs(nlist[left] + nlist[right])
        a,b = nlist[left],nlist[right]
    
    if nlist[left] + nlist[right] < 0:
        left +=1
    else:
        right -=1
        
print(a,b)