BOJ 7423 합이 0인 네 정수

www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

처음 봤을 때  Naive하게 생각하는 것으로 문제를 풀면서 해를 얻어갔다.

 

가장 처음 생각나는 풀이는 4중 for문으로 푸는 방법이었고, 이는 시간 복잡도가 O(n^4) 으로 n >= 4000 이였기 때문에 다른 문제들에 비해 넉넉했던 12초도 부족하여 문제 풀이에 적합하지 않았다.

여기서 첫번째로 생각났던 것은 4개의 합을 한꺼번에 찾는 것이 아니라, 2개의 합 + 2개의 합 으로 나누어 생각하여 그 이후에 생각해보기로 했다.

위의 방법은 시간복잡도가 O(2 * n^2) 으로 시간내에는 구할 수는 있다. 

위의 방법대로 구한 두개의 배열을 보면서 들었던 의식의 흐름은 다음과 같다.

 "이걸 사용해서 다시 이중 for문으로 모든 경우를 찾는 것은 처음 생각했던 Naive 한 방법이랑 똑같으니 의미 없는 짓이다. 생각해보니 이 두 배열에서 하나씩 가져와 합친 값이 0이라는건데, 그러면 모든 경우를 생각할 필요없이 배열을 정렬해서 A와B를 더한 경우의 수를 담은 배열은 는 앞에서부터,  C와 D를 더한 경우의 수를 담은 배열은 뒤에서 부터 탐색하면서 합해보자. 

  만약 AB[i] + CD[j] > 0 이면 i를 오른쪽으로 옮기고, AB[i] + CD[j] < 0 이면 j를 왼쪽으로 옮기면서 탐색하면 되겠다. 합이 0이라면 정답에 추가해주면 되겠다"

위의 생각대로 구현한다면 시간복잡도 O(nlog n + n) 으로,  총 시간 복잡도는 O(n^2 + n log n +n) 이 된다.

 

아래는 내 제출 코드이다.

#include <cstdio>
#include <algorithm>

long long AB[16000000], CD[16000000];
long long A[4000], B[4000], C[4000], D[4000];
long long answer = 0;


void sum(long long* a, 
         long long* b, 
         long long* result, 
         int n){

    int index = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            result[index++] = a[i] + b[j];
        }
    }
    std::sort(result, result + n*n);

}

int main(){
    int n; scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lld%lld%lld%lld",A+i, B+i, C+i, D+i);
    }
    sum(A,B,AB, n);
    sum(C,D,CD, n);


    int i=0, j = n*n -1;
    
    while(i < n*n && j >= 0){
        
        int local_sum = AB[i] + CD[j];
        if(local_sum > 0) --j;
        else if(local_sum < 0) i++;
        else{
            long long count1 = 1;
            long long count2 = 1;
            ++i, --j;
            while(i < n*n && AB[i] == AB[i-1]){ 
                ++i, ++count1;
            }
            while(j >= 0 && CD[j] == CD[j+1]){
                --j, ++count2;
            }
            
            answer += count1*count2;
        }
    }
    printf("%lld\n",answer);
    

}

 

 

ps. 실행시간 1등은 신기하게 풀었던데, 변수가 의미하는것을 알지 못해서 어떻게 돌아가는지 잘 모르겠다...