[백준][7453][C++] 합이 0인 네 정수

링크

https://www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

해설

4개의 배열을 2개로 만드는 작업을 해야 합니다.

1번 2번  ||  3번 4번

이때 오른쪽은 미리 합을 다 구해둔 후 2진 search 를 위해 정렬을 해둡니다.

 

다음 각 왼쪽에서 모든 경우의 수에 대해 loop 를 돌립니다.

이때 오른쪽은 이미 정렬이 되어있으므로 upper_bound lower_bound 를 이용하여 2진탐색을 합니다.

 

그 후 값의 합이 0이면 upp - low 한 값을 정답에 더해줍니다.

 

4가지 배열을 각 2개씩 나눠서 계산 횟수를 줄이는 게 주목적입니다.

 

코드

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

long long NUM = 0;
int TABLE[4][4000];

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

	for (int i = 0; i < N; ++i) {
		cin >> TABLE[0][i] >> TABLE[1][i] >> TABLE[2][i] >> TABLE[3][i];
	}

	vector <int> v;

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

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

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			int now = TABLE[0][i] + TABLE[1][j];
			int low = lower_bound(v.begin(), v.end(), -now) - v.begin();
			int upp = upper_bound(v.begin(), v.end(), -now) - v.begin();
			if (v[low] == -now) {
				NUM += upp - low;
			}
		}
	}

	cout << NUM;

	return 0;
}