[백준] 합이 0인 네 정수 (7453번)

문제

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

출력

합이 0이 되는 쌍의 개수를 출력한다.

---

이분탐색으로 분류가 되어 있는데 어디가 이분탐색인지 의아했으나, 풀이를 보고 납득했다.

풀이법은 A,B 배열을 합하고, C, D 배열을 합해서 두 배열로 압축한다.

두 배열의 합이 0이 되는 쌍의 수를 구하면 된다.

전처리로 C, D 배열을 합해서 벡터에 넣어놓은 후 A, B 배열의 합에 -를 곱해준 것과 같은 인덱스의 위치를 구해서 개수를 구한다.

 

lower_bound랑 upper_bound의 사용법을 알아두자.

lower_bound는 구하고자 하는 수의 시작 위치,

upper_bound는 구하고자 하는 수보다 큰 수의 시작 위치를 알려준다.

따라서 두 결과의 차로 원하는 수의 개수를 구하는 것이다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%ED%95%A9%EC%9D%B4%200%EC%9D%B8%20%EB%84%A4%20%EC%A0%95%EC%88%98%20(7453%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, p[4][4001];
vector<int> v;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) 
		for (int j = 0; j < 4; j++)
			cin >> p[j][i];

	for (int i = 0; i < N; i++) 
		for (int j = 0; j < N; j++) 
			v.push_back(p[2][i] + p[3][j]);

	sort(v.begin(), v.end());

	long long res = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int target = p[0][i] + p[1][j];
			int lo = lower_bound(v.begin(), v.end(), -target) - v.begin();
			int hi = upper_bound(v.begin(), v.end(), -target) - v.begin();
			if (-target == v[lo])
				res += (hi - lo);
		}
	}
		
	cout << res;
}