백준 2473. 세 용액

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

2473번: 세 용액

 

이전에 푼 두용액이랑 비슷한데 이번에는 3가지 용액의 합이 0에 가깝도록 한다.

또한 두 용액은 용액의 최대갯수가 10만개였는데, 

이 문제는 최대갯수가 5000개 이므로 O(N^2)까지도 가능하다는 것을 알수 있다.

 

처음에 생각한 방법은 left를 왼쪽끝, right를 오른쪽 끝으로 하고,

left 용액과 right 용액과 left+1 부터 right-1까지의 용액을 하나씩 더해보면서 0과 가까운 용액들을 갱신해준다.

그 후 left와 right의 합이 0보다 크다면 right을 왼쪽으로, 작다면 left를 오른쪽으로 옮겼다.

이 방법은 정답 판정을 받지 못했다.

 

정답 판정을 받은 방법은 하나의 용액 i를 정하고,

left를 i+1, right를 n-1로 하고,

합한 결과에 따라 left와 right를 조절하면서 용액들을 갱신시키는 방법이다.

그 후 i값을 증가시키면서 계속 탐색한다.