합이 0인 네 정수

음.. 문제보면서 가장간단하게 푸는방법은 아무래도 그냥 4중포문 돌리는게 제일 쉽겠지만,

배열의 크기가 4000에, 이걸 4승한다면... 시간제한 2초는 당연히 날거같아서, 그냥 2중포문 + 2중포문으로 나눠서 하는게 좋겠다고 생각이들었다.

 

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	vector<int> a(n);
	vector<int> b(n);
	vector<int> c(n);
	vector<int> d(n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
	}
	vector<int> first, second;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			first.push_back(a[i] + b[j]);
			second.push_back((c[i] + d[j]));
		}
	}
	sort(second.begin(), second.end());
	long long ans = 0;
	for (int num : first) {
		auto range = equal_range(second.begin(), second.end(), -num);
		ans += range.second - range.first;
	}

	printf("%lld\n", ans);
	return 0;
}

 

다음과 같이 나눠서풀었는데, 배열 대신 벡터를 사용한이유는 Sorting함수와 range를 사용하기 위해서 사용했다,.

range.second - range.first 를 통해 계속해서 합계산해서 검사를해보는과정 또한 벡터일때 쓰기 편해서 사용했다.

처음에 long long 말고 int 썼을때 틀렸는데, 아무래도 4000가지 의 값들을 다 더하고 일일이 검사하는 과정중

 int 를 초과하는게 아닌가 싶어서 long long으로 데이터 타입을 변경하고나서 정답을 확인했다.