[BOJ 7453 // C++] 합이 0인 네 정수

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 7453번 문제인 합이 0인 네 정수이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

이 문제는 주어진 네 배열 A, B, C, D에서 index를 하나씩 골라 그 위치의 정수들의 합이 0이 되는 경우의 수를 구하는 문제이다.

주어진 예제의 배열 A에서 보이듯, 이 문제는 각 배열에 중복원소가 등장할 수 있다.

index를 고르는 경우의 수를 구하는 것이기에 위 경우의 중복원소는 다 따로 계수해야 한다.

 

이 문제를 풀기 위해 다음과 같은 코드를 구상한다.

1) A와 B의 각 원소의 합으로 구성된, 길이 n^2 배열 AB를 만든다. [O(n^2)]

2) C와 D의 각 원소의 합에 -1을 곱한 길이 n^2 배열 CD를 만든다. [O(n^2)]

배열 AB와 CD를 이용하면 이 문제를 배열 AB의 원소와 CD의 원소에서 같은 원소를 찾는 문제로 생각할 수 있다.

3) AB와 CD를 크기순으로 정렬한다. [O(n^2 logn)]

4) 투 포인터로 문제를 해결한다.

AB의 0번 원소를 가리키는 ptab와 CD의 0번 원소를 가리키는 ptcd를 만든다.

둘이 가리키는 원소가 같다면, AB에 있는 그 원소의 개수와 CD에 있는 그 원소의 개수를 포인터를 옮기며 센다.

그 곱을 ans변수에 더해준다.

ptab가 가리키는 원소가 작다면 ptab를 한칸 옮기고, ptcd가 가리키는 원소가 작다면 ptcd를 한칸 옮긴다.

두 포인터중 하나가 배열을 벗어날 때까지 위 내용을 반복한다.

 

문제의 제약조건에서 네 수의 합이 int 범위를 넘어갈 수 없다는 것을 알 수 있으나, ans의 값은 int 범위를 넘어갈 수 있음에 유의한다. 글쓴이는 이 점을 놓쳐 오답을 여러 번 제출했다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;

int A[4000];
int B[4000];
int C[4000];
int D[4000];
int AB[16000000];
int CD[16000000];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n; // 배열 A,B,C,D를 읽어오기
    cin >> n;
    int a, b, c, d;
    for (int i = 0;i < n;i++) {
        cin >> a >> b >> c >> d;
        A[i] = a;
        B[i] = b;
        C[i] = c;
        D[i] = d;
    }
    for (int i = 0;i < n;i++) { // 배열 AB 계산
        for (int j = 0;j < n;j++) {
            AB[n * i + j] = A[i] + B[j];
        }
    }
    for (int i = 0;i < n;i++) { // 배열 CD 계산
        for (int j = 0;j < n;j++) {
            CD[n * i + j] = -(C[i] + D[j]);
        }
    }
    sort(AB, AB + (n * n)); // AB와 CD 정렬
    sort(CD, CD + (n * n));
    long long ans = 0; // ans, 투포인터로 사용할 변수 선언
    int abpt = 0;
    int cdpt = 0;
    while (abpt < n * n and cdpt < n * n) { // 두 포인터 모두 배열 범위에 들어있을 동안 반복
        if (AB[abpt] == CD[cdpt]) { // 같은 경우
            int x = AB[abpt];
            int c1 = 0, c2 = 0;
            while (AB[abpt] == x) { // AB에서 포인터를 옮기면서 같은 원소의 개수 c1을 센다
                abpt++;
                c1++;
                if (abpt == n * n) break; // 포인터가 배열을 넘어가는 경우 예외처리
            }
            while (CD[cdpt] == x) { // CD에서 포인터를 옮기면서 같은 원소의 개수 c2를 센다
                cdpt++;
                c2++;
                if (cdpt == n * n) break; // 포인터가 배열을 넘어가는 경우 예외처리
            }
            ans += (long long) c1 * (long long) c2; // 
        }
        else if (AB[abpt] < CD[cdpt]) abpt++; // 다른 경우 작은 수를 가리키는 쪽 포인터를 옮긴다
        else cdpt++;
    }
    cout << ans;
}