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

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

3151번: 합이 0

---

합이 0 문제는 이분 탐색으로 해결할 수 있습니다. 

N이 최대 10,000이기 때문에 10000C3은 = (10000 * 9999 * 9998) / 3!입니다. 

따라서, 3중 for문 이용하여 모든 경우의 수에 대해 합이 0이 되는지 확인하는 경우 시간 초과가 발생할 수 있습니다. 

 

두 수 A, B를 선택한 후 (A + B) * -1이 몇개인 지 찾으면 됩니다. 

⚠️ 10000C3이므로 주어진 코딩 실력 Ai가 모두 0인 경우, 경우의 수가 int형의 범위를 벗어날 수 있기 때문에

long long형을 사용해야합니다. 

 

아래는 전체 코드입니다. 

// 소요 시간 : 40분
#include <bits/stdc++.h>
using namespace std;

int c[10010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for(int i = 0; i < n; i++) cin >> c[i];

    sort(c, c + n);
    
    long long ans = 0;
    for(int i = 0; i < n - 2; i++){
        for(int j = i + 1; j < n - 1; j++){ // 두 수를 선택
            int s = c[i] + c[j];    // 두 수의 합
            int l = lower_bound(c + (j + 1), c + n, s * -1) - c;
            int u = upper_bound(c + (j + 1), c + n, s * -1) - c;
            ans += u - l;   // s * -1의 개수를 더해줌
        }
    }
    cout << ans;
}