[백준] Q2143 두 배열의 합 Gold III

https://www.acmicpc.net/problem/2143

2143번: 두 배열의 합

 

1. 문제의 접근과 유형

이분탐색, 누적합

 

주어진 어떤 배열 A에서 부배열의 합은 A[i] + ... + A[j] 를 말한다.

A의 부 배열합과 B의 부 배열의 합을 더해 T가 되는 '모든 부 배열 쌍의 개수' 를 구하시오.

 

말이 부 배열의 합이라 어려울 수 있지만 쉽게 생각하면

 >> 어떤 배열 X와 어떤 배열 Y의 원소들의 합이 X인 쌍의 개수를 구하시오. 인 문제입니다.

그러한 어떤 배열 X이 원소들이 부 배열의 합 이기 때문에 이를 구하기 위해 누적합을 사용합니다.

sum[j] - sum[i-1] = A[i] + A[i+1] ... A[j].

 

그리고 이러한 배열이 문제에서 주어진 조건에 따르면, n = 1000이고 이 배열에서의 누적합 개수는

(N+1) * N / 2이라 최대 500500개. (중복 제외 단순 개수)

A배열 500500개와 B배열 500500 개의 쌍을 구해봐야하면 매우 큽니다.

여기서 만족하는 값을 빠르게 찾기 위해 이분탐색을 사용합니다.

 

2. 문제의 접근

어떠한 배열 X와 Y 의 원소 합이 T인 쌍의 개수를 구하기 위해 누적합을 사용하고,

어떠한 배열 X에서의 값 x에 대해 T-x의 위치를 Y에서 빠르게 찾아야합니다.

 

2.1 이분탐색을 사용한 접근 (code 에서 solutionByBinarySearch)

  부 배열의 합은 하나만 나오는 것이 아니라 같은 값이 중복으로 나올 수 있습니다.

  1개가 아니라 여러개 있을 수도 있습니다.

  이를 해결하기 위해 upper_bound와 lower_bound를 사용하여 해당 값의 개수를 찾아냅니다.

upper_bound와 lower_bound는 링크 에서 찾아볼 수 있습니다.

 

2.2 Map을 통한 접근 (code 에서 solution)

 이분탐색으로 결국 구하려고 하는 것은 어떤 중복된 값의 '개수'였습니다.

우리는 이를 Map을 통해 값을 기록해두고, T-x의 값이 Map에 있는지 확인하면서

답을 더해주면 해결할 수 있습니다.

 

package solvedac.level5.gold3;

/*
2022.01.15 
문제번호 : Q2143     
이름 및 난이도 : 두 배열의 합 Gold III
문제이해 
-----------------
주어진 배열 A, B에 대해 A의 부배열과 B 부배열의 합이 T가 되는 모든 부 배열의 쌍의 개수를 구하시오.
sum = A[a] + B[b] 라고 할 때, 

 sum == target일 때는 값을 키운다. 또는 작게한후 다시 진행.
제한 조건 : 
  주어지는 T의 범위는 Int형 범위
  1<=N<=1000
접근 방법 :
   >> HashMap사용 why? N*M의 구현?
   https://nahwasa.com/entry/%EB%B0%B1%EC%A4%80-2143-%EC%9E%90%EB%B0%94-%EB%91%90-%EB%B0%B0%EC%97%B4%EC%9D%98-%ED%95%A9-BOJ-2143-JAVA
   참조

   >> 이분탐색.
    https://emoney96.tistory.com/36#recentComments
    참조

    상태공간의 이해.
     >> 우리가 가지고 놀 데이터의 공간은 결국 구간합들의 모임.

     + 중복 연산 의 경계
      1. 방법은 일단 왜안되는지도 모르겟는데 
        구조적으로 연산이 중복된다는 점에서 문제가 되긴됨.
        왜안됨.?
        

        2. 둘다 Hash쓸 때 A.get(key) * B.get(T-key) 가되게 되는데
        이 때 int형 범위를 넘어갈 수 있음.
        like 1000C2 = 499500 인데
        499500 * 499500 이면 죽어야지. 이때 죽는거엿음.
        (항상 범위를 조심하자)
*/

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

public class Q2143 {
    static int N, M;
    static int[] A, B;
    static int T;
    static long ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        N = Integer.parseInt(br.readLine());
        A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        M = Integer.parseInt(br.readLine());
        B = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        solution();
        solveByBinarySearch();
        System.out.println(ans);
    }

    public static void solveByBinarySearch() {
        // Calc A subSum & sorting
        int[] ASum = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            ASum[i] = ASum[i - 1] + A[i - 1];
        }
        int[] subSumArr = new int[(N * (N + 1)) / 2];
        int idx = 0;
        for (int i = 1; i < N + 1; i++) {
            for (int j = 0; j < i; j++) {
                subSumArr[idx++] = ASum[i] - ASum[j];
            }
        }
        Arrays.sort(subSumArr);
        // While Calc B subSum
        // find From A
        int[] Bsum = new int[M + 1];
        for (int i = 1; i < N + 1; i++) {
            Bsum[i] = Bsum[i - 1] + B[i - 1];
        }
        for (int i = 1; i < M + 1; i++) {
            for (int j = 0; j < i; j++) {
                int t = Bsum[i] - Bsum[j];
                int left = lower_idx(T - t, subSumArr);
                int right = upper_idx(T - t, subSumArr);
                ans += (right - left);
            }
        }
        System.out.println(ans);
    }

    public static int lower_idx(int target, int[] arr) {
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static int upper_idx(int target, int[] arr) {
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    // HashMap
    public static void solution() {
        int left = 0;
        int tmp = 0;
        int[] Asum = new int[N + 1];
        int[] Bsum = new int[M + 1];
        HashMap<Integer, Integer> Amap = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> Bmap = new HashMap<Integer, Integer>();
        Asum[0] = 0;
        for (int i = 1; i < N + 1; i++) {
            Asum[i] = tmp + A[i - 1];
            tmp = Asum[i];
        }
        for (int i = 1; i < N + 1; i++) {
            for (int j = 0; j < i; j++) {
                Amap.put(Asum[i] - Asum[j], Amap.getOrDefault(Asum[i] - Asum[j], 0) + 1);
            }
        }

        tmp = 0;
        Bsum[0] = 0;
        ans = 0;
        for (int j = 1; j < M + 1; j++) {
            Bsum[j] = tmp + B[j - 1];
        }
        for (int i = 1; i < M + 1; i++) {
            for (int j = 0; j < i; j++) {
                int key = T - (Bsum[i] - Bsum[j]);
                if (Amap.containsKey(key)) {
                    ans += Amap.get(key);
                }
            }
        }

    }
}

3. 실수한 점.

A의 pointer (left, right)를 두고 B의 pointer(left, right)를 두고

A[left ~ right] 의 합과 B[left+right]의 합을 합하여 T보다 작다면

Math.min(A[right+1], B[right+1])과 같이 더해주는 것으로 생각을 했었습니다..

연속의 연속합이다. '쌍의 개수'가 아니었고, 이전에 계속 누적합을 left~right로만 풀었던 것도 오히려 독이 되었습니다.

 

'쌍의 개수'임을 인지하지 못했던 점이 큰 실수였고, 문제를 너무 대충 읽고 넘어간것도 컸습니다.