[백준] 25332 수들의 합 8 - Java

 

 

 

두 수열의 길이가 왜 같을까?

이 부분을 잘 생각해보자..

 

길이가 같은 두 수열을 입력받고, 두 수열의 값을 뺀 값을 가지는 새로운 수열을 정의하자.

 

새로 만들어진 수열에 대해 누적 합 배열을 구하고, 이 배열의 구간합이 0인 부분수열의 수를 구하자.

 

 

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));        
        StringBuilder sb = new StringBuilder();      
        
        int N = Integer.parseInt(br.readLine());

        int[] arr1 = new int[N + 1];
        int[] arr2 = new int[N + 1];
        long[] arr3 = new long[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=1; i<N + 1; i++){
            arr1[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());

        for(int i=1; i<N+1; i++){
            arr2[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=1; i<N+1; i++){
            arr3[i] = arr2[i] - arr1[i];
        }

        for(int i=1; i<N+1; i++){
            arr3[i] = arr3[i-1] + arr3[i];
        }

        long result = 0;
        long cnt = 0;

        HashMap<Long, Long> hm = new HashMap<>();

        for(int i=1; i<N+1; i++){
            if(arr3[i] == 0){
                result++;                
            }

            if(hm.containsKey(arr3[i] - 0)){
                cnt = hm.get(arr3[i] - 0);
            }else{
                cnt = 0;
            }
            
            result += cnt;

            long a = 1;
            
            if(hm.containsKey(arr3[i])){
                hm.put(arr3[i], hm.get(arr3[i]) + 1);
            }else{
                hm.put(arr3[i], a);
            }
        }

        System.out.println(result);
        
    }
}

 

 

int범위를 초과하는 경우가 있어 long타입을 사용하자.

 

수열 두 개를 더하거나 빼서 새로운 수열을 만드는 테크닉.. 수능 수학 공부할 때 많이 봤던 것 같다.