백준 3151
n명의 학생들 중에 합이 0이 되는 3인 그룹을 만들 수 있는 경우의 수를 구하면 된다.
이 때 코딩 실력이 동일한 학생들도 따로 카운팅을 해줘야 함으로
upper_bound - lower_bound를 해주면 된다.
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
cnt += (upper_bound(v + j + 1, v+n, -(v[i] + v[j])) - lower_bound(v+ j + 1, v+n, -(v[i] + v[j])));
}
}
여기서 포문의 범위가 이렇게 설정되는 이유는
예를 들어 -3 -1 0 4 4 5 의 학생들이 주어졌을 때
고른 두 학생의 실력이 -3, -1 이라고 한다면
-3 + (-1) = -4 -> 4에 대한 lower_bound을 3~6번 인덱스에서만 확인하면 된다.
만약 고른 두 학생의 실력이 -3, 0 이라고 한다면
-3 + 0 = -3 -> 3에 대한 lower_bound을 4~6번 인덱스까지만 확인
=> 두 학생 실력의 합의 마이너스 값에 대한 lower_bound을 이용해야 하기 때문에
2번 인덱스의 -1의 값은 그 값보다 커질 수 없기 때문에 lower_bound의 범위에서 제외해도 된다.
#include <bits/stdc++.h>
using namespace std;
int n;
long long cnt;
int v[10001];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) cin >> v[i];
sort(v,v+n);
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
cnt += (upper_bound(v + j + 1, v+n, -(v[i] + v[j])) - lower_bound(v+ j + 1, v+n, -(v[i] + v[j])));
}
}
cout << cnt << '\n';
}