[백준] 7453번 합이 0인 네 정수

문제 설명

• https://www.acmicpc.net/problem/7453
• Gold 2

문제 풀이

• 문제는 중간에서 만나기를 이용하여 풀이하였다.
• 완전 탐색의 경우 4000^4의 경우로 시간초과가 발생한다.
• 첫 시도로 A, B그룹의 경우의수 C, D그룹의 경우의수를 모두 구하고, CD는 HashMap으로 두어 AB그룹을 순회하며 찾았지만 시간초과가 발생했다.
• 두번쨰로는 CD그룹의 배열을 정렬하여 AB그룹을 순회하며 이분탐색을 이용해 풀이하여 통과되었다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[] A, B, C, D;
    static int[] AB, CD;

    // val 이상인 값이 처음 나오는 인덱스
    static int lowerbound(int val) {
        int lo = -1;
        int hi = N*N;
        while (lo + 1 < hi) {
            int mid = (lo + hi) / 2;
            if (val < CD[mid]) hi = mid;
            else if (val > CD[mid]) lo = mid;
            else hi = mid;
        }
        return hi;
    }

    // val 초과인 값이 처음 나오는 인덱스
    static int upperbound(int val) {
        int lo = -1;
        int hi = N*N;
        while (lo + 1 < hi) {
            int mid = (lo + hi) / 2;
            if (val < CD[mid]) hi = mid;
            else if (val > CD[mid]) lo = mid;
            else lo = mid;
        }
        return hi;
    }


    static void solve() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        B = new int[N];
        C = new int[N];
        D = new int[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            A[i] = Integer.parseInt(st.nextToken());
            B[i] = Integer.parseInt(st.nextToken());
            C[i] = Integer.parseInt(st.nextToken());
            D[i] = Integer.parseInt(st.nextToken());
        }

        AB = new int[N*N];
        CD = new int[N*N];
        int ind = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                AB[ind] = A[i] + B[j];
                CD[ind++] = -(C[i] + D[j]);
            }
        }

        Arrays.sort(CD);

        //이분 탐색
        long res = 0;
        for (int i = 0; i < N*N; i++)
            res += (upperbound(AB[i]) - lowerbound(AB[i]));

        bw.write(res + "\n");
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        solve();
    }
}

/**
 * 합이 0인 네정수 (19:25)
 *
 * - N : 배열의 길이 (N <= 4000)
 * - an <= 2^28 (약 3억)
 *
 *
 * - 완전 탐색 필요 -> 4000^4 (시간초과)
 * - 두 집단으로 나눔 -> 4000^2
 * - 한 집단의 합 -> 다른 집단의 합 배열 이분탐색 진행
 *
 * N
 * a1 b1 c1 d1
 * ...
 * an bn cn dn
 */