3151 - 합이 0

문제

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

느낀점

응용 투포인터 문제, 포인터가 하나 늘어나면 이분탐색으로 찾을 수 있다. 합이 0이 되는 조건을 생각하는 게 어려웠는데, 문제의 상황을 더 잘 이해하자

풀이

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> arr(N);
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());
    long long answer = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            int sum = arr[i] + arr[j];
            answer +=
                upper_bound(arr.begin() + j + 1, arr.end(), -sum) - lower_bound(arr.begin() + j + 1, arr.end(), -sum);
        }
    }
    cout << answer;

    return 0;
}