백준 / BOJ / 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] 

입력

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

출력

첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.

해설

이 문제의 경우 굉장히 까다로웠습니다. 

1. 누적합을 이용할 때 단순히 순차적이 배열의 합이 아닌 배열의 합에 대한 모든 케이스를 ArrayList에 저장해야합니다.

2. 투포인터 개념을 이용하여 효율성을 향상시켜야합니다.

3. 1번에 대한 모든 케이스가 ArrayList에 저장되기 때문에 최악의 수를 생각하면 cnt를 long으로 지정해줘야 합니다.

 

이렇게 두가지를 지켜주면 생각보다 쉽게 해결할 수 있습니다. 저 같은 경우에도 3번을 제대로 생각하지 못하여 틀렸습니다.

 

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder("");

    static int T, N, M;
    static int[] A, B;
    static ArrayList<Integer> A_sum, B_sum;

    static void input() throws IOException {
        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());
    }

    static void process(){
        A_sum = new ArrayList<>();
        B_sum = new ArrayList<>();

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

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

        Collections.sort(A_sum);
        Collections.sort(B_sum);

        int L = 0, R = B_sum.size()-1;
        long ans = 0;

        while(L<A_sum.size() && R>=0){
            int sum = A_sum.get(L) + B_sum.get(R);
            if(sum == T){
                int valueA = A_sum.get(L);
                int valueB = B_sum.get(R);
                long aCnt = 0, bCnt = 0;
                while(L<A_sum.size() && valueA == A_sum.get(L)){
                    aCnt += 1;
                    L+=1;
                }
                while(R>=0 && valueB == B_sum.get(R)){
                    bCnt += 1;
                    R-=1;
                }
                ans += aCnt * bCnt;
            }else if(sum < T) L+=1;
            else R-=1;
        }

        System.out.println(ans);
    }

    public static void main(String[] args) throws IOException{
        input();
        process();
    }
}

 

<링크>

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