[백준 2143] 두 배열의 합(Java)

문제 링크 : https://www.acmicpc.net/problem/2143

이 문제는 누적합과 투 포인터로 풀 수 있습니다.

이 문제의 풀이 방법은 모든 누적합 가짓수를 뽑은 후 정렬하여 값을 T와 같게끔 조정하는 것입니다.

각 배열 별 모든 누적합을 구하는 방법은 이중 for문을 이용하여 i는 0부터 배열 길이까지, 그리고 j는 i부터 배열 길이까지 반복하여 나오는 수를 모두 더해 리스트에 저장합니다.

이후 A 누적합 리스트와 B 누적합 리스트를 각각의 포인터를 설정하여 한 쪽은 작은 순서대로, 다른 한 쪽은 큰 순서대로 가리키면서 값이 T보다 작다면 작은 포인터를 증가시키고, 크다면 큰 포인터를 감소시킵니다. 만약 같다면 누적합이 같은 값의 경우의 수를 고려해야 하기 떄문에 각각의 누적합과 같은 누적합 개수를 구한 후 이를 곱한 값을 최종 카운트합니다.

다음은 코드입니다.

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

class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long T = Long.parseLong(br.readLine());

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

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

        List<Long> SA = new ArrayList<>();
        set(SA,A);
        List<Long> SB = new ArrayList<>();
        set(SB,B);

        long res = 0;
        int a = 0;
        int b = SB.size()-1;
        while(a<SA.size() && b>=0){
            long sa = SA.get(a);
            long sb = SB.get(b);
            long sum = sa+sb;

            if(sum < T) a++;
            else if(sum > T) b--;
            else{
                // 중복되는 값 카운트
                long ea = 0;
                while(a<SA.size() && sa==SA.get(a)){
                    a++;
                    ea++;
                }

                long eb = 0;
                while(b>=0 && sb==SB.get(b)){
                    b--;
                    eb++;
                }

                res += ea*eb;
            }
        }
        System.out.println(res);
    }

    static void set(List<Long> sum, int[] arr){
        for(int i=0;i<arr.length;i++){
            long val = 0;
            for(int j=i;j<arr.length;j++){
                val += arr[j];
                sum.add(val);
            }
        }
        Collections.sort(sum);
    }
}