[백준 3151번] 합이 0 (C++)

문제링크 : https://www.acmicpc.net/problem/3151

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N;
int arr[10001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<N; i++) cin >> arr[i];

    sort(arr, arr+N);
    
    ll result = 0;
    for(int i=0; i<N; i++)
    {
        for(int j=i+1; j<N; j++)
        {
            int tmp = arr[i] + arr[j]; //2개 합 (고정)
            int idx_lower = lower_bound(arr+j+1, arr+N, -tmp) - arr; //tmp 이상
            int idx_upper = upper_bound(arr+j+1, arr+N, -tmp) - arr; //tmp 초과
            result += idx_upper - idx_lower; //가능한 갯수 저장
        }
    }

    cout << result;

    return 0;
}

 

3가지 합이 0이 되는 경우를 찾아야 한다.

이를 위해 2가지 값을 고정 (2가지 값의 합) 시켜 놓고 나머지 1개의 값을 이분 탐색을 통해 찾아준다.

이분 탐색을 위해 입력한 값을 정렬해주고 시작한다.

 

2개의 합을 구하면 3개의 합이 0이 되어야 하므로 나머지 값은 자동으로 알 수 있다.

(합이 tmp라 하면, 구하는 값은 자동으로 -tmp [tmp +(-tmp) = 0])

따라서 lower_bound와 upper_bound를 이용하여 해당 -tmp 값이 나오는 위치와 -tmp 초과하는 값의 위치를 찾아준다.

해당 위치 값들 이용해 -tmp에 해당하는 값이 몇 개 존재하는지 카운팅하는 것이 가능하다.

 

이렇게 구한 갯수들을 result에 저장해준다.

이때 result의 값은 범위에 따라 int 를 초과하는 경우가 발생하여 longlong으로 선언해준다.

이후 해당 result 값을 출력해주면 되낟.