[백준 / Java] 2142번 : 두 배열의 합

문제

한 배열 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 

5
4
1 3 1 2
3
1 3 2

예제 출력 1 

7

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

2143번: 두 배열의 합

---

문제 풀이

 해당 문제는 두 배열의 연속 합을 구하여 두 연속 합 배열을 투포인터 알고리즘으로 두 합을 구하는 문제이다.

 

 각 배열의 부 배열의 합 모든 경우를 구한 다음 T에 맞는 원소들을 매칭해주면 된다. N개의 원소를 갖는 배열의 부 배열의 크기는 n*(n-1)/2이므로 두 배열의 부배열을 구하는 데 걸리는 시간 O(N^2)이다. 그런 다음 두 부 배열 원소의 합이 T가 되는 값들을 매칭시켜주면 된다. 

 

투 포인터 방법으로는 두 배열의 합이 T가 되는 구간을 한 칸씩 이동하면서 탐색해주면 된다. 중복되는 원소도 처리해주기 때문에 빠르게 탐색이 가능하다.

1. aSum은 0번째 부터 탐색을 시작한다. bSum은 bSize-1부터 탐색을 시작한다.
2. 두 원소의 합을 구한다. sum = aSum[left] + bSum[right]
   1. sum == t  : t와 일치한다면 각 중복되는 원소의 크기를 구해 카운트 해준다. 
   2. sum > t    : t보다 크다면 수가 작아져야 되므로 right --;
   3. sum < t    : t보다 작다면 수가 커져야 하므로 left++; 

---

풀이 코드

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


public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static StringTokenizer st;
	public static StringBuilder sb = new StringBuilder();
	public static int INF = 100_000_000;

	
	public static void main(String[] args) throws IOException{
		long answer = 0;
		int N = Integer.parseInt(br.readLine());
		
		int A = Integer.parseInt(br.readLine());
		int[] Aarr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		int B = Integer.parseInt(br.readLine());
		int[] Barr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		ArrayList<Long> Asum = new ArrayList<>();
		ArrayList<Long> Bsum = new ArrayList<>();
		
		for(int i = 0; i < A; i++) {
			long temp = 0;
			for(int j = i ; j < A; j++) {
				temp+=Aarr[j];
				Asum.add(temp);
			}
		}
		for(int i = 0; i < B; i++) {
			long temp = 0;
			for(int j = i ; j < B; j++) {
				temp+=Barr[j];
				Bsum.add(temp);
			}
		}
		
		Asum.sort(null);
		Bsum.sort(null);

		int left = 0;
		int right = Bsum.size()-1;
		
		while(left < Asum.size() && right >= 0) {
			long sum = Asum.get(left) + Bsum.get(right);
			if(N == sum) {
				long curA = Asum.get(left);
				long Acount = 0;
				while(left < Asum.size() && curA == Asum.get(left)) {
					left++;
					Acount++;
				}
				
				long curB = Bsum.get(right);
				long Bcount = 0;
				while(right > -1 && curB == Bsum.get(right)) {
					right--;
					Bcount++;
				}
				answer += Acount * Bcount;
			}else if(N > sum) {
				left++;
			}else {
				right--;
			}
		}
		System.out.println(answer);
	}
}