[알고리즘] C++ 백준 7453 합이 0인 네 정수

백준 7453

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

7453번: 합이 0인 네 정수

풀이 전 나의 생각

정수로 이루어진 크기가 같은 배열 A, B, C, D가 주어지는데

이 때 A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구해야한다.

 

조건

- n (1 ≤ n ≤ 4000)

- 배열에 들어있는 정수의 절댓값은 최대 2^28

 

과정

n은 4000까지 주어지지만 a, b, c, d 총 4개의 값을 확인하며 탐색 시

4중 for 문을 사용해야 한다. 그러면 4000 * 4000 * 4000 * 4000이라는 어마무시한

계산 횟수가 나오게 되기 때문에 이분탐색을 이용하여 풀어야 한다.

 

배열에 들어있는 정수의 최대 값은 2^28, 약 2억이기 때문에 데이터 타입은 int로 설정한다.

 

 

1. A, B 배열과 C, D 배열의 합을 미리 구해준다.

for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			left_val.push_back(A[i] + B[j]);
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			right_val.push_back(C[i] + D[j]);
		}
	}

현재 0이 될 수 있는 모든 쌍을 구해야하기 때문에 결국엔 모든 경우의 수를 탐색해야한다.

 

여기서 4중 for문을 이용하여 모든 경우를 탐색해버리면 앞에서 말했듯이 엄청난 계산 횟수로 인하여

시간 제한을 맞추지 못하기 때문에 2중 for문으로 AB의 합과 CD의 합을 구하고 어느 한 부분을 기준으로

이분탐색을 진행하여 풀어내야한다.

 

결론은 A,B,C,D를 4중 for문을 통해 모든 경우의 수를 구하기 보다는 AB의 경우의 수 + CD의 경우의 수로

모든 경우의 수를 구하여 이분 탐색을 진행하는 것이 효율적이다.

 

2. AB의 합을 기준으로 0이 되는 값을 BC의 합에서 이분 탐색으로 찾아낸다.

for (int i = 0; i < left_val.size(); i++)
	{
		int upper = upper_bound(right_val.begin(), right_val.end(), -left_val[i]) - right_val.begin();
		int lower = lower_bound(right_val.begin(), right_val.end(), -left_val[i]) - right_val.begin();

		ans += (upper - lower);
	}

AB 합의 모든 경우를 탐색하며 BC 합의 모든 경우에서 AB합의 마이너스 값 즉, AB + (-AB) = 0 이 될 수 있는

값을 이분 탐색으로 찾아낸다. (-AB = Tartget)

 

upper와 lower를 구해주는 이유는 중복되는 모든 경우의 수를 더해주기 위해서다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int A[4001];
int B[4001];
int C[4001];
int D[4001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	long long ans = 0;

	cin >> n;

	vector<int>left_val;
	vector<int>right_val;

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

		A[i] = a;
		B[i] = b;
		C[i] = c;
		D[i] = d;
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			left_val.push_back(A[i] + B[j]);
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			right_val.push_back(C[i] + D[j]);
		}
	}
	sort(left_val.begin(), left_val.end());
	sort(right_val.begin(), right_val.end());

	for (int i = 0; i < left_val.size(); i++)
	{
		int upper = upper_bound(right_val.begin(), right_val.end(), -left_val[i]) - right_val.begin();
		int lower = lower_bound(right_val.begin(), right_val.end(), -left_val[i]) - right_val.begin();

		ans += (upper - lower);
	}

	cout << ans;
	return 0;
}