백준 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가지 경우가 있다.

 

 

 

 

풀이

---

conpulake.tistory.com/90

백준 2632 (피자판매)

 

위의 문제에서 조각을 선택하는 방식에서 힌트를 얻었다.

static void getSum(long[] arr, List<Long> sum_List, int idx, long sum) {
				
	sum_List.add(sum);
	
	idx++;
	
	if(idx < arr.length) {
		getSum(arr, sum_List, idx, sum + arr[idx]);
	}
	
}

 

위 문제와 다른점은 직선배열에서의 합을 구하는 것이기 때문에

arr.length 까지의 합을 구하면 된다.

 

나머지는 위의 문제와 동일하게 A합 리스트와 B합 리스트를 양쪽 끝에서 부터 이분탐색을 하면 된다.

<전체코드>

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

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	
	static long T;
	static int n, m;
	static long[] A, B;
	static List<Long> A_Sum, B_Sum;
	static long answer = 0;
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(bufferedReader.readLine());
		
		n = Integer.parseInt(bufferedReader.readLine());
		A = new long[n];
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		for(int i = 0 ; i < n ; i++) {
			A[i] = Long.parseLong(st.nextToken());
		}
		A_Sum = new ArrayList<Long>();
		for(int i = 0 ; i < n ; i++) {
			getSum(A, A_Sum, i, A[i]);
		}
		
		
		m = Integer.parseInt(bufferedReader.readLine());
		B = new long[m];
		st = new StringTokenizer(bufferedReader.readLine());
		for(int i = 0 ; i < m; i++) {
			B[i] = Long.parseLong(st.nextToken());
		}
		B_Sum = new ArrayList<Long>();
		for(int i = 0 ; i < m ; i++) {
			getSum(B, B_Sum, i, B[i]);
		}
		
		Collections.sort(A_Sum);
		Collections.sort(B_Sum);
		
		int left = 0, right = B_Sum.size() -1;
		while(left < A_Sum.size() && right >= 0) {
			
			long leftSum = A_Sum.get(left);
			long rightSum = B_Sum.get(right);
			
			if(leftSum + rightSum == T) {
				long leftCount = 0;
				long rightCount = 0;
				while(left < A_Sum.size() && leftSum == A_Sum.get(left)) {
					leftCount++;
					left++;
				}
				
				while(right >= 0 && rightSum == B_Sum.get(right)) {
					rightCount++;
					right--;
				}
				
				answer += leftCount * rightCount;
			}
			
			if(leftSum + rightSum < T) {
				left++;
			}
			
			if(leftSum + rightSum > T){
				right--;
			}
		}
		
		System.out.println(answer);
	}
	
	static void getSum(long[] arr, List<Long> sum_List, int idx, long sum) {
				
		sum_List.add(sum);
		
		idx++;
		
		if(idx < arr.length) {
			getSum(arr, sum_List, idx, sum + arr[idx]);
		}
		
	}
	
}

 

이 문제는 풀이 자체는 쉬웠는데 자료형을 long으로 두어야한다는 점에서 혼자 삽질을 했다.

자료형을 틀려서 틀렸다고 나오는 경우 백준은 디버깅을 할 수가 없어서 정말 어렵다.

 

마지막 결과가 Long 으로 나오기 때문에 그사이사이 모든 자료형을 Long으로 두어야한다.