풀이 요약

투 포인터를 활용한 문제.

풀이 상세

1. 배열 $A$ 와 배열 $B$ 에서 나올 수 있는 모든 수열의 합을 누적합 리스트에 넣어두자.

2. 누적합 리스트 $A$ , $B$ 를 정렬하고 $A=0$ 에서 $B=B.size()-1$ 에서 탐색을 시작한다.

3. 해당 두 포인트의 값을 더한 경우 나오는 값은 3개이다.

   • 임의의 합 $sum$ 이 $T$ 보다 작은 경우

     • 누적합 리스트는 동일한 경우가 존재한다. 따라서 현재 값보다 $AList$ 에서 큰 값이 나올 때까지 계속 $APoint$ 를 높여주자.

   • 임의의 합 $sum$ 이 $T$ 보다 큰 경우

     • a 와 마찬가지로, 현재 값보다 $BList$ 에서 작은 값이 나올 때 까지 계속 $BPoint$ 를 줄여주자.

   • 임의의 합 $sum$ 이 $T$ 와 동일한 경우

     • 현재 $APoint$ 와 $BPoint$ 와 동일한 수를 해당 $List$ 에서 모두 찾아야 한다. 해당 수를 곱하여 $ans$ 에 더해주자.

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int T, N, M;
    static int[] A, B;
    static List<Long> AList, BList;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        StringTokenizer stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(stk.nextToken());
        }
        M = Integer.parseInt(br.readLine());
        B = new int[M];
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            B[i] = Integer.parseInt(stk.nextToken());
        }

        AList = new ArrayList<>();
        for (int i = 0; i < A.length; i++) {
            long tmp = 0;
            for (int j = i; j < A.length; j++) {
                tmp += A[j];
                AList.add(tmp);
            }
        }

        BList = new ArrayList<>();
        for (int i = 0; i < B.length; i++) {
            long tmp = 0;
            for (int j = i; j < B.length; j++) {
                tmp += B[j];
                BList.add(tmp);
            }
        }

        Collections.sort(AList);
        Collections.sort(BList);
        int Apoint = 0;
        int Bpoint = BList.size() - 1;
        long ans = 0;
        while (Bpoint >= 0 && Apoint < AList.size()) {
            long sum = AList.get(Apoint) + BList.get(Bpoint);
            if (sum < T) {
                int curr = Apoint;
                while (Apoint < AList.size() && AList.get(Apoint) <= AList.get(curr)) Apoint++;
            } else if (sum > T) {
                int curr = Bpoint;
                while (Bpoint >=0 && BList.get(Bpoint) >= BList.get(curr)) Bpoint--;
            } else {
                int currA = Apoint;
                int currB = Bpoint;
                long cntA = 0;
                long cntB = 0;
                while (Apoint < AList.size() && AList.get(Apoint) <= AList.get(currA)) {
                    Apoint++;
                    cntA++;
                }
                while (Bpoint >=0 && BList.get(Bpoint) >= BList.get(currB)) {
                    Bpoint--;
                    cntB++;
                }
                ans += cntA * cntB;
            }
        }
        System.out.println(ans);
    }
}