[BOJ 2295] 세 수의 합

이분탐색에서 자주 쓰이는 테크닉이므로 기억해두자.

이 문제는 $a[i] + a[j] + a[k] = a[l]$ 에서 $a[l]$ 이 최대가 되는 $a[l]$ 을 출력해야한다. 

맨 처음 생각할 수 있는건 $O(N^4)$ 방법인데 당연히 시간초과가 나므로 pass. 그 다음은 $O(N^3log{N})$ 으로 먼저 $(i,j,k)$ 쌍 들을 모두 돌아보면서 이 합에 대해 $a[l]$ 을 이분탐색 하는 방법이 있다. 하지만 이것도 시간초과가 난다. 

이제 여기서 쓸 수 있는 테크닉이, 2개의 값을 묶어서 하나의 값에 대해 이분탐색을 돌려주면 된다.

이게 가능한 이유는 우리는 어차피 $(i,j,k)$ 쌍들은 상관 없고 정답을 만족 시키는 $a[l]$ 에만 관심이 있기 때문에, 미리 전 처리 해놓는거랑 비슷하다고 보면 된다. 그럼 $O(N^2log{N})$ 에 해결이 가능하다. 아마 문제를 많이 안 풀어봐서 모르지만 n개의 값을 묶어서 응용할 수 있을 것 같은데 좀 더 풀어보면 알거같다.