[백준 3151] 합이 0

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

값이 중복되지 않게 예외 처리를 해줘야 하는데 이 점을 내가 간과해서 꽤나 애를 먹었다.

풀이 과정

1. 세 수를 합해야 하므로 모든 수를 따지면 $N^3$이므로 시간 초과이다.
2. 그러나 두 수를 더하고 0에 수렴하는 나머지 수를 찾는다면 $N^2logN$이 된다. n<10000이므로 $N^2$은 1억이라 4초안엔 어지간하면 해결될 것 같다.
3. 그래서 나는 두 수를 찾는 이중 포문과 두 값과 더했을 때 0이 되는 값을 이진 탐색으로 찾았다.
4. 다만 같은 값이 여러개 있어도 모두 독립된 값이므로 이를 예외처리 하기 위해 upper_bound - lower_bound 하여 개수를 더하였다.
5. 또한 0번배열부터 순차적으로 조합해 나가므로 m번 배열에선 m-1번 배열까지는 쳐다 볼 필요도 없다. 이를 예외처리 해줘야 한다.

구현

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
    int n;
    cin>>n;
    int arr[10000];
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    sort(arr,arr+n);
    long long cnt=0;
    for(int i=0; i<n-2; i++){
        for(int j=i+1; j<n-1; j++){
            int tmp = arr[i] + arr[j];
            int lower = lower_bound(arr +(j+1), arr + n, -tmp) - arr;
            int upper = upper_bound(arr+(j+1), arr + n, -tmp) - arr;
            cnt +=  upper - lower ; 
        }
    }
    cout<<cnt;
    return 0;
}