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

문제

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

7453번: 합이 0인 네 정수

---

문제 요약

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

A[a], B[b], C[c], D[d]의 합이 0이 되는 쌍의 개수를 출력한다.

 

+ 각 배열의 크기 n은 1이상 4000이하이다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>

#define MAX_N 4000

using namespace std;

int n;
int arr[4][MAX_N + 1];

vector<int> sum_ab, sum_cd;

void input() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		arr[0][i] = a;
		arr[1][i] = b;
		arr[2][i] = c;
		arr[3][i] = d;
	}
}

void solve() {
	// 배열 A와 B, C와 D를 통해 나올 수 있는 모든 합들을 저장
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sum_ab.push_back(arr[0][i] + arr[1][j]);
			sum_cd.push_back(arr[2][i] + arr[3][j]);
		}
	}

	// 오름차순 정렬
	sort(sum_ab.begin(), sum_ab.end());
	sort(sum_cd.begin(), sum_cd.end());

	// sum_ab와 sum_cd의 길이가 최대 16,000,000이므로 cnt는 최대 16,000,000 * 16,000,000이 가능
	long long cnt = 0;

	// -sum_ab[i]와 같은 값이 sum_cd에 몇 개 있는지 모두 체크 (합이 0이어야 하므로)
	for (int i = 0; i < sum_ab.size(); i++) {
		// -sum_ab[i]가 sum_cd에 처음 등장하는 인덱스 탐색
		int cd_pre = lower_bound(sum_cd.begin(), sum_cd.end(), -sum_ab[i]) - sum_cd.begin();
		
		// -sum_ab[i]가 sum_cd에 마지막에 등장하는 인덱스 탐색
		int cd_end = upper_bound(sum_cd.begin(), sum_cd.end(), -sum_ab[i]) - sum_cd.begin();
		
		cnt += (cd_end - cd_pre);
	}

	cout << cnt;
}

int main() {
	input();
	solve();
}

---

코드 설명

1. 배열 A, B, C, D를 입력 받는다.

 

2. 배열 A와 B, 배열 C와 D를 통해 나올 수 있는 모든 합들을 저장하는 배열 sum_ab, sum_cd를 생성한다.

 

3. lower_bound, upper_bound를 사용하기 위해 두 배열을 오름차순 정렬한다.

 

4. -sum_ab[i]가 sum_cd에 존재하는 개수를 모두 센다.

+ 개수가 최대 4000 × 4000 × 4000 × 4000 이므로 long long형을 사용한다.