Algorithm/이분탐색
백준 3151 합이0 c++ // 이분탐색, nC3최적화하는법
Mini_96
2024. 3. 25. 00:21
https://www.acmicpc.net/problem/3151
3151번: 합이 0
Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다.
www.acmicpc.net
1. 의사코드
1. 이진탐색범위 : j+1부터 탐색한다
2. UpperBbound-LowerBbound가 합이3인사람의 숫자이다. //중복없는
※ 3이 없는경우 ub==lb가 되어 0명이다.
2.전체코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ret;
int n;
vector<ll> v;
set<tuple<int, int, int>> s;
int vis[10004];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0;i<n;++i){
ll tmp;
cin >> tmp;
v.push_back(tmp);
}
sort(v.begin(), v.end());
//for (auto i : v) cout << i << " ";
//cout << "\n";
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
int cur = v[i] + v[j];
//cout << cur << " ";
int lb = lower_bound(v.begin()+j+1, v.end(), -1 * cur)-v.begin();
int ub = upper_bound(v.begin()+j+1, v.end(), -1 * cur) - v.begin();
ret += ub - lb;
}
}
cout << ret;
return 0;
}