[baekjoon] 7453

합이 0인 네 정수 

문제

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

출력

합이 0이 되는 쌍의 개수를 출력한다.

예제 입력

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

예제 출력

5

 

풀이

이전에 풀었던 2470번 두 용액 문제와 비슷하다고 생각했다. 두 용액 문제는 주어진 수들 중 두 수의 합이 0에 가까운 수의 순서쌍을 찾는 문제였다. 2470번을 풀때는 정렬 후 처음과 끝을 가리키는 두 포인터를 설정하고 두 수의 합에 따라 포인터를 이동하는 방식으로 문제를 풀었었다. 

 

근데 이번 문제는 수가 총 4가지로 분류되어 있어서 두 포인터를 어떻게 설정할지가 문제였다. 

두 포인터를 적용하기 위해서 4가지로 분류된 수를 2개씩 묶어서 2가지로 만들었다.

(A B C D 배열이 있으면 A B로 만들 수 있는 순서쌍의 합과 C D로 만들 수 있는 순서쌍의 합)

 

함수 자료형을 int로 해서 몇분동안 삽질했다..

 

#include <iostream>
#include <algorithm>

using namespace std;

int **input, n;
long long * combine1, * combine2;

bool compare(long long a, long long b)
{
    if(a > b)return true;
    else return false;
}

void init()
{
    cin >> n;
    input = new int *[4];

    for(int i = 0; i < 4; i++)input[i] = new int[n];
    for(int i = 0; i < n; i++)cin >> input[0][i] >> input[1][i] >> input[2][i] >> input[3][i];

    combine1 = new long long [n*n];
    combine2 = new long long [n*n];
}

void combine()
{
    int index = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++, index++){
            combine1[index] = input[0][i] + input[1][j];
            combine2[index] = input[2][i] + input[3][j];
        } 
    }
    sort(combine1, combine1+(n*n));
    sort(combine2, combine2+(n*n), compare);
}

long long solve()
{
    long long cnt = 0;
    int ptr1 = 0, ptr2 = 0;

    while(ptr1 != n*n && ptr2 != n*n)
    {
        long long sum = combine1[ptr1] + combine2[ptr2];

        
        if(sum == 0)
        {
            int temp1 = combine1[ptr1];
            int temp2 = combine2[ptr2];
            long long cnt1 = 0, cnt2 = 0;
            while(ptr1 != n*n && combine1[ptr1] == temp1)ptr1++, cnt1++;
            while(ptr2 != n*n && combine2[ptr2] == temp2)ptr2++, cnt2++;

            cnt += cnt1 * cnt2;
        }
        else
        {
            if(sum > 0)ptr2++;
            else ptr1++;
        }
    }
    return cnt;
}

int main()
{
    init();
    combine();

    cout << solve();
}