[백준 7453번] 합이 0인 네 정수 (C++)

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

4개의 배열 A,B,C,D가 주어졌을 때 해당 배열들에서 수를 하나씩 선택했을 때 선택한 수들의 합이 0인 경우가 몇가지인지 구하는 문제다.

나이브하게 4중포문으로 구현이 가능하긴 하지만 아무리 제한시간이 12초라도 4000을 네 번 곱하면(N⁴) 시간초과가 당연하다.(N = 1억에 1초로 생각하면 된다)

 

아이디어는 선형대수학을 떠올렸는데 선형대수학에서 ABx = C의 방정식을 풀때 행렬 AB를 구하는 과정에 O(N³)이 걸리기 때문에 Bx를 치환함으로써 O(N²) 두번으로 문제를 해결했었다.

 

이 문제도 4중포문 대신 AB의 모든 경우의 수를 계산하고(O(N²)), CD의 모든 경우의 수를 계산해서(O(N²)) AB배열과 CD배열을 투포인터로 접근(O(N))해서 최종 O(N²) 의 시간복잡도로 해결하였다.

 

 

#include <iostream>
#include <algorithm>
#define lint long long
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    int arr[4][4001];
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 4; j++){
            cin >> arr[j][i];
        }
    }
    const int SIZE = 16000000;
    int *ab = new int[SIZE];
    int *cd = new int[SIZE];
    int len = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            ab[len] = arr[0][i]+arr[1][j];
            cd[len] = arr[2][i]+arr[3][j];
            len++;
        }
    }
    sort(ab,ab+len);
    sort(cd,cd+len);
    int left = 0, right = len-1;
    lint cnt = 0;
    while(left < len && right >= 0){
        if(ab[left]+cd[right] == 0){
            int tmpAB = ab[left], tmpCD = cd[right];
            lint cntAB = 0, cntCD = 0;
            //tmpAB와 같은수의 개수 카운트
            while(left < len && tmpAB == ab[left]){
                cntAB++;
                left++;
            }
            //tmpCD와 같은수의 개수 카운트
            while(right >= 0 && tmpCD == cd[right]){
                cntCD++;
                right--;
            }
            cnt += (cntAB*cntCD);
            continue;
        }
        if(ab[left]+cd[right] > 0){
            right--;
        }
        else if(ab[left]+cd[right] < 0){
            left++;
        }
    }
    cout << cnt;
}