[코딩테스트 C++] 합이 0인 네 정수

오늘의 문제

합이 0인 네 정수

접근 방식

• 4000개가 최대인 입력이 4번 곱해지면 시간초과가 나므로, 2개씩 더하여 합의 경우를 모두 만든다.
• 그리고 0이되는 경우만을 검색하여 있는 개수만큼 더한다.
• 왼쪽 합에 대해 오른쪽 합의 합이 0이 될 수 있는것이 1개 이상일 수 있으므로, lower_bound, upper_bound알고리즘을 이용하여 뺀 값을 더한다.

나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#pragma warning(disable: 4996)
using namespace std;

int n, m;
const int MAX = 4000;
int arr[MAX][4];
//bool visit[MAX][MAX] = {false, };
//int dx[] = {-1, 1, 0, 0};
//int dy[] = {0, 0, 1, -1};

int main(){
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%d %d %d %d",&arr[i][0], &arr[i][1], &arr[i][2], &arr[i][3]);
    }
    vector<int> a, b;
    for(int i=0;i<n;i++){
        for (int j=0; j<n; j++) {
            a.push_back(arr[i][0] + arr[j][1]);
            b.push_back(arr[i][2] + arr[j][3]);
        }
    }
    long long answer = 0;
    sort(b.begin(), b.end());
    for(int i=0;i<a.size();i++){
        int num = (-1) * a[i];
        int l = lower_bound(b.begin(), b.end(), num) - b.begin();
        int u = upper_bound(b.begin(), b.end(), num) - b.begin();
            answer += u-l;
    }
    cout<<answer<<endl;
    return 0;
}

다른 풀이

#include<cstdio>
#include<algorithm>
#pragma warning(disable:4996)
int n, a[4][4001];
int sum[2][16000001];

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < 4; j++) 
			scanf("%d", &a[j][i]);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 2; k++)
				sum[k][i*n + j] = a[k * 2][i] + a[k * 2 + 1][j];
		}
	}

	for (int k = 0; k < 2; k++) 
		std::sort(sum[k], sum[k] + n * n);
	
	int lo = n * n, up = n * n;
	long long ans = 0;
	for (int i = 0; i < n*n; i++) {
		while (lo != 0 && sum[1][lo - 1] >= -sum[0][i]) lo--;
		while (up != 0 && sum[1][up - 1] > -sum[0][i]) up--;
		ans += (up - lo);
	}
	printf("%lld", ans);
}

배울 점