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

문제

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

7453번: 합이 0인 네 정수

문제풀이

A에서 하나, B에서 하나, C에서 하나, D에서 하나를 무조건 골라 합이 0인 개수를 구하는 문제이다.

이중 for문으로 A와 B를 하나씩 고른 값을 sumAB에 저장, C와 D를 하나씩 고른 값을 sumCD에 저장한다.

upper, lower bound를 이용하기 위해 각 벡터를 오름차순으로 정렬한다.

for문으로 sumAB를 탐색하면서 sumCD에서 -sumAB[idx]의 값이 있는지 확인을 한다.

upper_bound-lower_bound를 하여 개수를 구한다.

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N(0);

	cin >> N;
	vector<long long>A(N, 0);
	vector<long long>B(N, 0);
	vector<long long>C(N, 0);
	vector<long long>D(N, 0);

	int idx1(0), idx2(0);
	for (idx1 = 0; idx1 < N; ++idx1)
		cin >> A[idx1] >> B[idx1] >> C[idx1] >> D[idx1];

	vector<long long>sumAB(N * N, 0);
	vector<long long>sumCD(N * N, 0);

	int idx3(0);
	for (idx1 = 0; idx1 < N; ++idx1)
		for (idx2 = 0; idx2 < N; ++idx2) {
			sumAB[idx3] = A[idx1] + B[idx2];
			idx3++;
		}

	idx3 = 0;
	for (idx1 = 0; idx1 < N; ++idx1)
		for (idx2 = 0; idx2 < N; ++idx2) {
			sumCD[idx3] = C[idx1] + D[idx2];
			idx3++;
		}

	sort(sumAB.begin(), sumAB.end());
	sort(sumCD.begin(), sumCD.end());

	long long answer(0);

	for (idx1 = 0; idx1 < sumAB.size(); ++idx1)
		answer += (upper_bound(sumCD.begin(), sumCD.end(), -sumAB[idx1]) -
			lower_bound(sumCD.begin(), sumCD.end(), -sumAB[idx1]));

	cout << answer;
}