BOJ 3151: 합이 0

#BOJ 3151: 합이 0

3151번: 합이 0

#풀이

간단하게 3개의 숫자를 더해서 0이 되는 숫자를 찾는 문제이다.

 

이분탐색에서 중복된 수의 개수를 구하는 방법은 upper_bound() - lower_bound() 를 하면 숫자가 몇개 중복되어 있는 확인할 수 있다.

 

사실 그냥 간단하게 2개의 숫자를 고르고 남은 숫자를 찾으면 해결할 수 있는 문제이다.

 

맨 처음에는 next_permutation으로 해결하려고 했다가 중복되어 숫자를 고르는게 너무 많아 결과값이 너무 많게 나왔다....

 

#코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<int> arr;
vector<int> arr1;
int arr_[10002];
long long ans;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}
	sort(arr.begin(), arr.end());

	for (int i = 0; i < n-1; i++) {
		for (int j = i + 1; j < n; j++) {
			ans = ans + (upper_bound(arr.begin()+j+1, arr.end(), -1 * (arr[i] + arr[j]))
				- lower_bound(arr.begin()+j+1, arr.end(), -1 * (arr[i] + arr[j])));
		}
	}
	cout << ans << '\n';
	return 0;
}