Baekjoon #7453

Baekjoon #7453

1개의 풀이 · Java

문제 원문 보기 ↗

SOLUTION INFO

Java · Main.java

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

public class Main {
	public static void main(String[] args) throws Exception {
        FastReader rd = new FastReader();

		int N = rd.nextInt();

		int[][] a = new int[N][4];
		for (int i = 0; i < N; i++) {
			a[i][0] = rd.nextInt();
			a[i][1] = rd.nextInt();
			a[i][2] = rd.nextInt();
			a[i][3] = rd.nextInt();
		}

        int[] ab = new int[N * N];
		int idx = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				ab[idx++] = a[i][0] + a[j][1];
			}
		}

		Arrays.sort(ab);
        long ans = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int cd = a[i][2] + a[j][3];
				ans += upperBound(ab, -cd) - lowerBound(ab, -cd);
			}
        }
		
         System.out.println(ans);

    }


    private static int lowerBound(int[] ab, int val) {
		int l = 0;
		int r = ab.length - 1;

		while (l <= r) {
			int mid = (l + r) / 2;

			if (ab[mid] >= val) {
				r = mid - 1;
			} else
				l = mid + 1;
		}
		return r;
	}

	private static int upperBound(int[] ab, int val) {
		int l = 0;
		int r = ab.length - 1;

		while (l <= r) {
			int mid = (l + r) / 2;

			if (ab[mid] > val) {
				r = mid - 1;
			} else
				l = mid + 1;
		}
		return r;
	}

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
	}
}

SOLUTION DESCRIPTION

풀이 설명

1. 중간에서 만니기의 기초 문제. 여러 알고리즘을 활용한 풀이가 가능하겠으나, 공통적으로 $O(N^4)$ 의 시간복잡도를 $O(2N^2)$ 으로 만드는 설계에 대한 이해가 필요하다. 2. `a,b,c,d` 가 가진 각각의 정수가 합이 `0` 이 나오는 경우는 `(a+b)+(c+d)` 역시 `0` 이 나올수 밖에 없다. 따라서 기존 4개의 항목을 `ab,cd` 라는 2개의 항목으로 줄여 시간초과 문제를 해결하자. 3. 본 풀이의 경우, 이분탐색을 활용했다. `ab` 의 모든 경우의 합을 먼저 구한 후 이를 오름차순 정렬하여, `-cd` 의 값이 `ab` 의 요소에 존재하는지 확인하자. 4. 주어지는 정수의 최댓값은 $2^{28}$ 로, 4가지 정수의 덧셈으로는 `int` 를 넘지 않으나, 출력값은 `int` 를 넘을 수 있다. 모든 경우의 합이 `0` 이 나오는 입력이 있다고 가정한다면, 출력값은 최대 $4000^4 = 2.56e+14$ 가 되기 때문이다..