[BOJ] 백준 2143 두 배열의 합

[문제]

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

 

 

[소스 코드]

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));
		StringTokenizer st;
		long t = Long.parseLong(br.readLine());
		int n = Integer.parseInt(br.readLine());
		long[] a = new long[n];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			a[i] = Long.parseLong(st.nextToken());
			if(i>0) a[i] += a[i-1];
		}
		int m = Integer.parseInt(br.readLine());
		long[] b = new long[m];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<m;i++) {
			b[i] = Long.parseLong(st.nextToken());
			if(i>0) b[i] += b[i-1];
		}
		int numA = n*(n+1) / 2;
		int numB = m*(m+1) / 2;
		long[] sumA = new long[numA];
		long[] sumB = new long[numB];
		int idx = 0;
		for(int i=0;i<n;i++) {
			for(int j=i;j<n;j++) {
				long v = a[j];
				if(i>0) v -= a[i-1];
				sumA[idx++] = v;
			}
		}
		idx = 0;
		for(int i=0;i<m;i++) {
			for(int j=i;j<m;j++) {
				long v = b[j];
				if(i>0) v -= b[i-1];
				sumB[idx++] = v;
			}
		}
		Arrays.sort(sumA);
		Arrays.sort(sumB);
		int start = 0;
		int end = numB - 1;
		long result = 0;
		while(start<numA && end>=0) {
			long valA = sumA[start];
			long valB = sumB[end];
			long val = valA + valB;
			if(val == t) {
				long cntA = 0;
				long cntB = 0;
				while(start<numA && valA==sumA[start]) {
					cntA++;
					start++;
				}
				while(end>=0 && valB==sumB[end]) {
					cntB++;
					end--;
				}
				result += cntA * cntB;
			}
			else if (val<t) {
				start++;
			}
			else {
				end--;
			}
		}
		System.out.println(result);
	}
}