[BOJ]2473번: 세 용액

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

---

세 용액의 합이 0에 가까운 값을 구하는 문제입니다.

N^3으로 해결하면 시간초과가 나므로 이중 포문 + 이분 탐색을 활용해서 N^2(logN)으로 시간복잡도를 줄일 수 있습니다.

 

이분 탐색 조건은

현재 mid 인덱스를 사용해서 구한 세 용액의 합이 양수라면 mid 인덱스를 하한값(end)을 내림으로써 0에 가깝게 가도록 합니다.

현재 mid 인덱스를 사용해서 구한 세 용액의 합이 음수라면 mid 인덱스를 상한값(start)을 올림으로써 0에 가깝게 가도록 합니다.

 

추가로 주의할 점은 정수 3개를 더한 값이 정수 범위를 넘어갈 수 있으므로 long값으로 파싱해서 사용해야 합니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ2473.java