[Algorithm]Baekjoon 3151번 :: 합이 0

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
#include <mutex>
 
using namespace std;
 
 
int n;
vector<int> v;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    v.resize(n);
 
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i];
    }
 
    sort(v.begin(), v.end());
 
    long long answer = 0;
 
    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            int targetNum = (v[i] + v[j]) * -1;
 
            int lowerIndex = lower_bound(v.begin() + j + 1, v.end(), targetNum) - v.end();
            int upperIndex = upper_bound(v.begin() + j + 1, v.end(), targetNum) - v.end();
 
            answer += upperIndex - lowerIndex;
        }
    }
 
    cout << answer;
 
    return 0;
}
 
 
 
 
 

 

제한시간이 4초로 넉넉하기때문에, 숫자 두개의 조합을 완전탐색을 구하고 나머지를 이분탐색으로 구하면 된다.

최대 10000개의 숫자를 순서없이 2개를 선택해야하는 경우의 수는 10000C2 이기 떄문에, 대략 5천만 정도 된다.

 

이후 타겟이되는 숫자를 이분탐색으로 구해야하는데, 직접 구현해도되지만 굳이 그럴필요없이 STL의 lower_bound를 사용한다. 

단, 이 문제에서는 숫자가 중복되는 경우가 있고, 그것들도 전부 세어줘야 한다.

그렇기때문에 타겟숫자가 총 몇개인지를 알아야 한다.

그러기 위해서 upper_bound까지 구해줘서 upper_bound의 결과값인덱스에서 lower_bound 결과값인덱스를 빼주면,

타겟숫자의 개수를 구할 수 있다.