boj 2467 : 용액

boj 2467 : 용액

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

 

정렬된 정수 배열이 주어진다.

주어진 배열에서 2개의 정수를 뽑아 그 합을 0에 가장 가깝게 만들면 된다.

기본적으로 2개 모두 뽑아 확인하는 방법은 N^2이고, N이 10만이므로 시간 초과가 난다.

two pointer 방법을 이용한다.

 

*L+*R이 0보다 크다면 R을 감소시키며, *L+*R이 0보다 작다면 L을 증가시킨다.

 

Greedy + Two Pointer로 문제를 해결할 수 있다.

Greedy Solution으로 문제를 해결하기 위해서는 "순간 최적이 전체 최적이다."라는 것을 증명해야하나,

직관적으로만 알고, 증명하진 못하였다. 

-> Prove By Solving으로 증명했다^^;