[BOJ 2473] 세 용액 C++

 

2473번: 세 용액

 

 

문제풀이

 

용액들의 특성값이 주어졌을 때 세 개의 용액을 선택해서 특성값이 0에 가장 가까운 용액을 찾는 문제다.

 

용액의 특성값은 -1,000,000,000 이상 1,000,000,000 이하다.

세 용액들을 더하면 오버플로우가 날 수 있기 때문에 배열은 long long 자료형으로 선언해준다.

 

3SUM - Wikipedia

 

이번에는 세 용액을 더해주어야 하는데 투 포인터로 어떻게 세 개를 찾지,,고민이 하다가 위 링크를 보고 힌트를 얻을 수 있었다.

 

첫 번째 용액은 고정시켜 놓고 두 번째, 세 번째 용액을 투 포인터로 찾는 방법이다.

left는 첫 번째 용액 바로 다음 용액부터, right는 마지막 인덱스부터 탐색해나간다.

minDiff는 특성값과 0의 차, minLeft, minMid, minRight는 세 용액의 인덱스 정보이다.

 

세 용액의 합이 diff보다 작은 경우 정보를 갱신해준다.

세 용액의 합이 0이라면 특성값이 0에 가장 가까운 용액을 찾은 것이므로 탐색을 종료한다.

sum이 0보다 작으면 arr[left]값이 더 커져야 하므로 left++,

sum이 0보다 크면 arr[right]값이 더 작아져야 하므로 right++ 해준다.

 

 

C++ 코드