백준 2143

●문제 출처

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

●정리(요약)
한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

T(=5) = A[1] + B[1] + B[2]
= A[1] + A[2] + B[1]
= A[2] + B[3]
= A[2] + A[3] + B[1]
= A[3] + B[1] + B[2]
= A[3] + A[4] + B[3]
= A[4] + B[2]

●코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

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

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

        List<Integer> sumA = new ArrayList<>();
        List<Integer> sumB = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += A[j];
                sumA.add(sum);
            }
        }

        for (int i = 0; i < m; i++) {
            int sum = 0;
            for (int j = i; j < m; j++) {
                sum += B[j];
                sumB.add(sum);
            }
        }

        Collections.sort(sumA);
        Collections.sort(sumB);

        int left = 0;
        int right = sumB.size() - 1;
        long count = 0;

        while (left < sumA.size() && right >= 0) {
            int sum = sumA.get(left) + sumB.get(right);

            if (sum == T) {
                int a = sumA.get(left);
                int b = sumB.get(right);

                long leftCount = 0;
                long rightCount = 0;

                //같은 수 세기
                while (left < sumA.size() && sumA.get(left) == a) {
                    leftCount++;
                    left++;
                }

                while (right >= 0 && sumB.get(right) == b) {
                    rightCount++;
                    right--;
                }

                count += leftCount * rightCount;
            } else if (sum < T) {
                left++;
            } else {
                right--;
            }
        }

        System.out.println(count);
    }
}

●느낀 점

이해하면 쉬운데, 생각해내기 까지 너무 어렵다 ㅠㅠ
두배열이 합친 누적합인줄 알았으나 아니였다...
두개 배열을 각각 누적합들의 리스트를 만들고 왼쪽 오른쪽 포인터를 증가 감소 해주고 같은 수가 있을 경우도 계산해줘야함.