[백준] BOJ_2143 두 배열의 합

1. 문제 정보

• 문제 요약: 두 개의 정수 배열 와 가 주어졌을 때, 의 부 배열(Sub-array)의 합과 의 부 배열의 합을 더해서 가 되는 모든 부 배열 쌍의 개수를 구하는 문제입니다.
• 난이도: Gold 3
• 링크: 백준 2143번 - 두 배열의 합

---

2. 접근 방식

이 문제는 단순한 완전 탐색으로 접근하면 시간 초과가 발생하기 쉬운 문제입니다. $N$과 $M$의 크기를 고려하여 효율적인 탐색 전략을 수립해야 합니다.

2.1 문제의 본질 분석 (Complexity Analysis)

입력 크기는 $N, M \le 1,000$입니다.만약 $A$의 모든 부 배열과 $B$의 모든 부 배열을 일일이 구해서 비교한다면 어떻게 될까요?

• $A$의 부 배열 개수: 약 $\frac{N(N+1)}{2} \approx 500,000$개
• $B$의 부 배열 개수: 약 $\frac{M(M+1)}{2} \approx 500,000$개
• 단순 이중 루프 비교 시 연산 횟수: $500,000 \times 500,000 = 2,500억 (2.5 \times 10^{11})$이는 제한 시간(2초) 내에 절대 불가능한 수치입니다. 따라서 우리는 $O(N^2)$ 수준의 전처리 후, $O(\log N)$ 혹은 $O(1)$ 수준의 탐색을 수행하는 알고리즘이 필요합니다.

2.2 알고리즘 설계: 전처리(Preprocessing)와 이분 탐색(Binary Search)

문제를 해결하기 위해 다음 두 단계로 로직을 나눕니다.

1. 부 배열의 합 리스트 생성 (Preprocessing):
   와 각각에 대해 가능한 모든 부 배열의 합을 구해 별도의 리스트(sumA, sumB)에 저장합니다. 이 과정은 $O(N^2)$과 $O(M^2)$이 소요되지만, 일 때 충분히 수행 가능합니다.
2. 정렬 및 이분 탐색 (Sort & Binary Search):
   두 리스트 중 하나(여기서는 sumB)를 오름차순 정렬합니다.
   그리고 sumA를 순회하며, 값이 sumB에 몇 개 존재하는지 찾습니다.
   이때, sumB에는 중복된 합의 값이 존재할 수 있습니다. 따라서 단순한 binarySearch가 아닌, 중복된 원소의 시작과 끝 위치를 찾는 Lower Bound(하한선)와 Upper Bound(상한선) 알고리즘을 사용해야 합니다.

2.3 수식 및 점화식

우리가 찾아야 하는 조건은 다음과 같습니다.

$Sum_A[i] + Sum_B[j] = T$

이를 변형하면 우리가 찾아야 할 타겟 값(Target)을 정의할 수 있습니다.

$Target = T - Sum_A[i]$

즉, sumA의 각 원소에 대해 sumB 내에서 값이 $Target$인 원소의 개수를 구하여 더하면 됩니다.

$Count = \text{UpperBound}(Target) - \text{LowerBound}(Target)$

---

3. 코드 구현 (Code)

아래 코드는 입력된 로직을 그대로 유지하되, 가독성을 위해 포맷팅을 다듬었습니다.

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int T, N, M;
    static int[] A, B;
    static long answer = 0;

    public static void main(String[] args) throws IOException {
        // 1. 입력 받기
        T = Integer.parseInt(br.readLine());

        N = Integer.parseInt(br.readLine());
        A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            A[i] = Integer.parseInt(st.nextToken());

        M = Integer.parseInt(br.readLine());
        B = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++)
            B[i] = Integer.parseInt(st.nextToken());

        // 2. 부 배열의 합 리스트 생성 (O(N^2))
        List<Long> sumA = getSumList(A);
        List<Long> sumB = getSumList(B);

        // 3. 이분 탐색을 위한 정렬 (sumB만 정렬해도 됨)
        Collections.sort(sumB);

        // 4. sumA를 순회하며 sumB에서 Target 값 찾기
        for (long a : sumA) {
            long target = T - a;

            // 중복된 값의 개수를 구하기 위해 Lower Bound와 Upper Bound 사용
            int low = getLowBound(target, sumB);
            int high = getUpperBound(target, sumB);

            answer += high - low;
        }

        System.out.println(answer);
    }

    // Lower Bound: 찾고자 하는 값(target) 이상의 값이 처음 나타나는 위치
    private static int getLowBound(long target, List<Long> list) {
        int left = 0;
        int right = list.size();

        while (left < right) {
            int mid = (left + right) / 2;

            if (target <= list.get(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    // Upper Bound: 찾고자 하는 값(target)을 초과하는 값이 처음 나타나는 위치
    private static int getUpperBound(long target, List<Long> list) {
        int left = 0;
        int right = list.size();

        while (left < right) {
            int mid = (left + right) / 2;

            if (target < list.get(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    // 배열의 모든 부 배열 합을 구하는 메소드
    private static List<Long> getSumList(int[] arr) {
        List<Long> list = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            long sum = 0;
            for (int j = i; j < arr.length; j++) {
                sum += arr[j];
                list.add(sum);
            }
        }

        return list;
    }
}

---

4. 회고 및 배운 점

4.1 시간 복잡도 개선의 중요성

이 문제는 자료구조를 변환하여 시간 복잡도를 획기적으로 줄이는 대표적인 예제입니다.

• Naive Approach: 시간 초과
• Prefix Sum + Binary Search: 통과

특히 sumB 리스트의 크기가 최대 약 50만 개이므로, 이를 정렬하는 비용()과 탐색 비용()이 전체 성능을 좌우합니다.

4.2 자료형 선택

문제 풀이 시 간과하기 쉬운 부분이 바로 데이터 타입입니다.

1. 부분 합(Partial Sum): 배열의 원소 값이 크거나, 이 커지면 int 범위를 넘어설 수 있습니다. 코드에서 List<Long>을 사용하여 오버플로우를 방지했습니다.
2. 결과 값(Answer): 가능한 쌍의 개수는 sumA의 크기 sumB의 크기까지 가능합니다.
   최악의 경우 $500,000 \times 500,000 = 2.5 \times 10^{11}$이므로, int 범위를 훨씬 초과합니다. 따라서 answer 변수는 반드시 long 타입을 사용해야 합니다.