BOJ 3151 - 합이 0

3151번: 합이 0 (acmicpc.net)

3151번: 합이 0

 

접근 방법

3개의 수의 합이 0이 되는 조합을 모두 찾는 문제이다.

 

2문제를 미리 다 더한 후, 마지막 하나를 이분탐색으로 구하는 문제이다.

 

이 문제를 처음할 때 실수한 부분이 중복되는 값을 고려하지 않은것이다.

만약,

 

8
-10 5 5 5 5 5 5 5

 

다음 케이스가 올 경우, 5를 모두 개별 취급을 해야하므로 21이 되어야 한다.

그러나, 이분탐색의 경우 중복을 처리하는게 쉽지 않기 때문에 lower_bound와 upper_bound의 도움을 받아야한다.

 

lower_bound로 0이 되는 가장 작은 Index의 주소를, upper_bound로 0이 되는 가장 큰 Index를 구한 후, 이 둘의 차를 최종 결과에 더하면 된다.

 

코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#include<map>

using namespace std;

int n;
long long arr[10001];

int main() {
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	sort(arr, arr + n);

	long long res = 0;
	for (int i = 0; i < n-2; i++) {
		for (int j = i + 1; j < n-1; j++) {
			long long sum = arr[i] + arr[j];

			long long l = lower_bound(arr + (j + 1), arr + n, -sum)- arr;
			long long r = upper_bound(arr + (j+1), arr + n, -sum) - arr;
			
			res += (r - l);
		}
	}


	cout << res;
	return 0;
}

중복되는 것을 고려할 땐, lower_bound와 upper_bound를 쓰자..