[백준/BOJ] 백준 7453번 : 합이 0인 네 정수

www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

AB에 A[i] + B[j] 조합의 모든 경우를 저장하고, CD에 C[i] + D[j] 조합의 모든 경우를 저장하여 각각 정렬한 뒤, AB를 돌면서, 해당 값과 합이 0이 되는 수를 lower_bound를 통해 찾고, 만약 찾았다면 it_upper(upper_bound한 것) - it_lower(lower_bound한 것)를 계산하여 개수를 추가한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<int> A;
vector<int> B;
vector<int> C;
vector<int> D;
vector<int> AB;
vector<int> CD;
vector<int>::iterator it;
vector<int>::iterator it_lower;
vector<int>::iterator it_upper;

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

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;

		A.push_back(a);
		B.push_back(b);
		C.push_back(c);
		D.push_back(d);
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			AB.push_back(A[i] + B[j]); //A[i] + B[j] 조합의 모든 경우를 저장
			CD.push_back(C[i] + D[j]); //C[i] + D[j] 조합의 모든 경우를 저장
		}

	sort(AB.begin(), AB.end());
	sort(CD.begin(), CD.end());

	long long cnt = 0;

	for (it = AB.begin(); it != AB.end(); it++)
	{
		int find_num = -(*it); //(*it)과 합이 0이 되는 수

		it_lower = lower_bound(CD.begin(), CD.end(), find_num);
		it_upper = upper_bound(CD.begin(), CD.end(), find_num);

		if (it_lower != CD.end()) //찾았을때
		{
			cnt += it_upper - it_lower;
		}
	}

	cout << cnt;


	return 0;
}