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

개요

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

7453번: 합이 0인 네 정수

골드2 난이도 문제다.

풀이

배열 4개에서 합이 0인 경우의 수를 구해야 한다.

n<=4000 이므로 브루트포스로 구한다면 O(4000^4) 으로 어마어마한 시간이 나오게 된다.

처음에 배열을 두 개씩 나누어 합치는 부분까지는 생각했다.

A, B, C, D 배열이 있다면 AB, CD 배열처럼 두 개씩 합치고 각각 정렬한다.

이후에는 투 포인터 혹은 이분 탐색으로 구현이 가능할 것 같다고 판단했다.

 

이분 탐색으로 구현했는데, 중복된 숫자를 찾는 과정에서 시간초과가 났다.

이분 탐색으로 계속 찾아나갔는데 그럴 필요가 없었다.

upper_bound, lower_bound를 이용하면 간단하게 구현할 수 있었다.

• upper_bound : 찾는 값 마지막 인덱스의 다음 인덱스 반환(초과한 값 인덱스)
• lower_bound : 찾는 값 첫 인덱스 반환

upper_bound - lower_bound 해주면 찾는 값이 몇 개가 있는지 간단하게 알 수 있다.

 

추가로 경우의 수가 int의 범위를 넘어갈 수 있음에 주의해야한다.

코드

#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
constexpr int LIMIT = 4002;

int n;
int A[LIMIT];
int B[LIMIT];
int C[LIMIT];
int D[LIMIT];
ll ans;
vector<int> AB;
vector<int> CD;


int main()
{
	cin.tie(0)->sync_with_stdio(0);

	cin >> n;
	AB.reserve(n * n);
	CD.reserve(n * n);

	for (int i = 0; i < n; i++)
		cin >> A[i] >> B[i] >> C[i] >> D[i];

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

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

	for (const auto& ab : AB)
	{
		int lb = lower_bound(CD.begin(), CD.end(), -ab) - CD.begin();
		int ub = upper_bound(CD.begin(), CD.end(), -ab) - CD.begin();
		ans += ub - lb;
	}
	cout << ans;
}