[java] 2143 두 배열의 합

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

1. 문제를 보면 A,B 배열에서 특정 범위 내의 연속된 값을 더해 T 값을 구한다.
2. 그럼 A 배열에서 나올 수 있는 모든 연속된 값을 구한다.
3. B 배열에서 나올 수 있는 모든 연속된 값을 더하면서, 나온값+A배열에 있는 값 = T 라면 count ++ 해주면 된다!

---

2번 과정부터 보자. (2. 그럼 A 배열에서 나올 수 있는 모든 연속된 값을 구한다.)
2-1. 누적합을 구한다.
2-2. 2중 반복문을 통해 나올 수 있는 모든 연속된 값을 구한다.
2-3. 구한 값을 HashMap 에 저장한다.

for (int i = 1; i <= n; i++) {
	for (int j = i; j <= n; j++) {
    	int rangeSum = arr[j]-arr[i-1];
        hm.put(rangeSum, !hm.containsKey(rangeSum) ? 1 : hm.get(rangeSum)+1);
        }
    }

3번 과정은
3-1. 누적합을 구한다.
3-2. 2중 반복문을 통해 나올 수 있는 모든 연속된 값을 구한다. (= sum 이라고 가정)
3-3. T - sum 이 hashMap 에 있다면 == 연속된 수의 합으로 T를 만들 수 있다는 뜻이므로 count ++

for (int i = 1; i <= n; i++) {
	for (int j = i; j <= n; j++) {
    	int rangeSum = arr[j]-arr[i-1];
    	int key = t-rangeSum;
    	if (hm.containsKey(key)) {
        	answer += hm.get(key);
        }
    }
}

3. 전체 코드

import java.io.*;
import java.util.*;
public class Main {

	static int T,N,M,arr[];
	static long count;
	static boolean visited[];
	
	public static int stoi(String str){
		return Integer.parseInt(str);
	}
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = stoi(br.readLine());

        N = stoi(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = new int[N+1];
		for(int i=1;i<=N;i++){
			arr[i] = arr[i-1] + stoi(st.nextToken());
		}

		HashMap<Integer, Integer> hm = new HashMap<>();
		for(int i=1;i<=N;i++){
			for(int j=i;j<=N;j++){
				int sum = arr[j]-arr[i-1];
				hm.put(sum, hm.getOrDefault(sum, 0)+1);
			}
		}

		M = stoi(br.readLine());
		st = new StringTokenizer(br.readLine());
		arr = new int[M+1];
		for(int i=1;i<=M;i++){
			arr[i] = arr[i-1]+stoi(st.nextToken());
		}

		for(int i=1;i<=M;i++){
			for(int j=i;j<=M;j++){
				int sum = arr[j]-arr[i-1];
				if(hm.containsKey(T-sum)) count += hm.get(T-sum);
			}
		}
		System.out.print(count);
    }
}