(C++) - 백준(BOJ) 3151 : 합이 0

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

3151번: 합이 0

이분탐색 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

학생 수 n, 정답을 출력할 변수 ans, 코딩 실력을 저장할 vector v를 선언한 후 적절히 입력받습니다. 이후 v를 오름차순으로 정렬해줍니다.

📔 풀이과정

n이 1만이므로 brute force로 3중 for loop를 수행하면 O(4억)이 넘어 4초 초과로 틀리게 됩니다.

O(n^2log(n))으로 2개의 수를 결정했으면 나머지 한 개의 수를 이분탐색으로 찾을 수 있습니다.

1. v[i], v[j]를 결정한 후 -(v[i], v[j])의 lower_bound와 upper_bound를 각각 찾습니다.

2. 두 값의 index차이가 곧 개수가 됩니다. 즉, v[i], v[j]를 결정한 시점에 나올 수 있는 경우의 수가 됩니다.

3. 그 값을 ans에 누적해 더해줍니다.

* ans는 long long이어야 합니다.

📔 정답출력

ans를 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll ans;
vector <int> v;

int main(){
    cin >> n;
    v.resize(n);

    for(int i = 0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());

    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            auto el = lower_bound(v.begin() + j + 1, v.end(), -(v[i] + v[j])) - v.begin();
            auto el2 = upper_bound(v.begin() + j + 1, v.end(), -(v[i] + v[j])) - v.begin();
            if(el == n) continue;
            if(v[i] + v[j] + v[el] == 0) ans += el2 - el;
        }
    }

    cout << ans;
}

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.