백준 g4 3151 합이 0 c++

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

3151번: 합이 0

 

문제

3명의 코딩실력의 합이 0이 되도록 할 때, 가능한 경우의 수 구하기

세 수의 합(https://kyj0032.tistory.com/51) 문제와 비슷해보이지만 다른 문제다

세 수의 합은 a+b+c=d 총 4개의 변수가 있다면

이 문제는 a+b+c = 0 3개의 변수가 있고, 원소가 중복되면 안 된다.

 

풀이

1. 경우의 수

먼저 두 명을 뽑고, 합이 0이 되게 하는 나머지 팀원이 있는지를 binary search로 찾는다.

2. 중복

같은 코딩 실력을 가진 사람이 여러 명 가능하므로, 몇 명 있는지는 upper_bound - lower_bound로 구한다.

 

주의할 점

학생 수가 10^4명이므로, 경우의 수는 int범위를 넘을 수 있다. long long으로 선언해주기

 

코드

/*boj g4 3151 합이 0*/
#include <algorithm>
#include <iostream>
#define MAXN 10005
using namespace std;

int N;
int arr[MAXN];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    sort(arr, arr + N);

    long long ans = 0;

    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            int sum = arr[i] + arr[j];
            int cnt = upper_bound(arr + j + 1, arr + N, -sum) - lower_bound(arr + j + 1, arr + N, -sum);

            ans += cnt;
        }
    }

    cout << ans << "\n";
}