백준 7453 합이 0인 네 정수

문제링크 : https://www.acmicpc.net/problem/7453

아이디어

• 접근 1. 배열 4개를 모든 경우의수로 더할경우
  • O(N^4) : 4000^4 > 시간초과
• 접근 2. 두개씩 더해서 이진탐색 사용 가능할까?
  • 두개씩 더한다음
  • 한개만 정렬을 해줌
  • 그다음 각각 더해서 0이되는 수를 찾기
  • 0이 되는 여러개가 있을 수 있잖아 > 마지막에 같으면 여러개 구하기
  • 시간복잡도
    • 두개씩 곱함 : N^2 * 2
    • 한개 정렬 : N^2 * lgN^2
    • 모든 수에대해 더해서 0이되는 수를 이진탐색으로 찾기 : N^2 * lgN^2
    • 더해서 0이 되는거 여러개 있을경우, 계속 더해주기 : N
    • 총합 : O(N^2 * 2 + N^2 * lgN^2 + N*2 * lgN^2 * N) = O(N^3 * lgN^2) = 64e9 * 20 > 시간초과
• 접근 3. 두개씩 더해서 투포인터 사용
  • 두개씩 더한 다음 모두 정렬
  • 각각의 배열에서 하나는 왼쪽(st)부터, 하나는 오른쪽(en)부터 시작해서 더해서 0이되는값 찾기
    • 더해서 0이 될경우, 각각 값이 같은 수 구해서 곱하기
    • 이떄, 더해서 0이될경우, 포인터 넘어가므로 O(N) 사용할 필요없음
  • 더해서 0보다 작을경우 st++, 클경우 en--

시간복잡도 계산

• 두개 더한다음 정렬 : N^2 * 2 + N^2*lgN^2 * 2
• 투포인터 수행 : N^2 * 2
• 총합 : O(N^22 + N^2lgN^22 + N^22) = O(N^2*lgN^2)

자료구조

• A,B,C,D 배열
  • 최대값 : 2^28 > INT 가능
• 두개씩 더해준 값 : AB, CD
  • 최대값 : 2^29 > INT 가능
• 합이 0이되는 쌍의 개수
  • 4000^4 > long long 사용

코드(C++)

#include <iostream>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
int A[4010];
int B[4010];
int C[4010];
int D[4010];
int AB[16000010];
int CD[16000010];
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    
    // 두개씩 더하기
    int k=0;
    for(int j=0; j<n; j++) {
        for(int i=0; i<n; i++) {
            AB[k] = A[j] + B[i];
            CD[k] = C[j] + D[i];
            k++;
        }
    }
    
    // 정렬
    sort(AB, AB+k);
    sort(CD, CD+k);
    
    ll cnt=0;
 
    int st = 0;
    int en = k-1;
    
    while(st <k && en >=0) {
        int sumv =AB[st] + CD[en];
        if(sumv == 0) {
            // 두개가 같은게 여러개 있을 수 있음
            // 같은 값을 곱해서 더해주기
            int originSt = st;
            int sameSt = 0;
            while(AB[st] + CD[en] == 0) {
                sameSt++;
                st++;
                if(st==k) break;
            }
           
            int sameEn = 0;
            while(AB[originSt] + CD[en] == 0) {
                sameEn++;
                en--;
                if(en<0) break;
            }
            cnt += sameSt * sameEn;
        } else if(sumv < 0) {
            st++;
        } else {
            en--;
        }
    }
    
    cout << cnt << '\n';
    return 0;
}
 

문제유형

• Two pointer - 두 배열의 pointer
  • 두배열의 합이나 곱으로 모든 경우의 수를 따져야할때
  • 양쪽에서 st, en놓고 올라가고 줄어드는 방법
  • 이때 조심해야할것 : 배열이 같은 값이 중복될 수 있음
  • 이떄 중복되는것 계산해줘야함