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

백준 7453 합이 0인 네 정수

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

• 배열 a, b, c, d의 합
  = 배열 a, b의 합과 배열 c, d의 합을 각각 구한 뒤, 둘을 더하여 구한다

upper_bound & lower_bound 이용 풀이

• sumAB[]에서 값이 -sumCD 인 원소의 수
  = upper_bound(sumAB, sumAB + (n $*$ n), -sumCD) - lower_bound(sumAB, sumAB + (n $*$ n), -sumCD)

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

//2^28 = 2^30 = (10^3)^3 = 10^9
const int MAXN = 4000 ;
const int MAXSIZE = 4000 * 4000;

int n;
long long a[MAXN + 1];
long long b[MAXN + 1];
long long c[MAXN + 1];
long long d[MAXN + 1];
long long sumAB[MAXSIZE + 1];

void getSumAB() {
	int idx = 0;
	for(int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j) {
			sumAB[idx] = a[i] + b[j];
			++idx;
		}
	return;
}

long long getCnt() {
	long long cnt = 0;
	long long sumCD;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j) {
			sumCD = c[i] + d[j];

			int lb = lower_bound(sumAB, sumAB + (n * n), -sumCD) - sumAB;
			int ub = upper_bound(sumAB, sumAB + (n * n), -sumCD) - sumAB;

			if (sumAB[lb] + sumCD == 0)
				cnt += (ub - lb);
		}
	return cnt;
}

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

	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	
	getSumAB();
	sort(sumAB, sumAB + (n * n));
	cout << getCnt();
	return 0;
}

투 포인터 알고리즘 이용 풀이

• 공부할 예정

📌참고자료

• 백준 7453 합이 0인 네 정수 풀이
  https://jaimemin.tistory.com/1108