boj 2143: 두 배열의 합

2020/07/13 - [알고리즘 공부] - boj 1208: 부분집합의 합2

boj 1208: 부분집합의 합2

 

위 문제와 완전 동일한 방법으로 풀면 됨

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t=in.nextInt();
		int n=in.nextInt();
		int A[]=new int[n];
		for(int i=0;i<n;i++) {
			A[i]=in.nextInt();
		}
		int m=in.nextInt();
		int B[]=new int[m];
		for(int i=0;i<m;i++) {
			B[i]=in.nextInt();
		}
		
		
		ArrayList<Integer> left=new ArrayList<Integer>();
		for(int i=0;i<A.length;i++) {
			int sum=0;
			for(int j=i;j<A.length;j++) {
				sum+=A[j];
				left.add(sum);
			}
		}
		ArrayList<Integer> right=new ArrayList<Integer>();
		for(int i=0;i<B.length;i++) {
			int sum=0;
			for(int j=i;j<B.length;j++) {
				sum+=B[j];
				right.add(sum);
			}
		}
		
		long ans=0;
		Collections.sort(left);
		Collections.sort(right);
		int leftIndex = 0;
		int rightIndex = right.size() - 1;
		while (leftIndex < left.size() && rightIndex >= 0) {
			int leftSum = left.get(leftIndex);
			int rightSum = right.get(rightIndex);

			if (leftSum + rightSum == t) {
				long leftSame = 0;
				while (leftIndex < left.size() && left.get(leftIndex) == leftSum) {
					leftIndex++;
					leftSame++;
				}
				long rightSame = 0;
				while (rightIndex >= 0 && right.get(rightIndex) == rightSum) {
					rightIndex--;
					rightSame++;
				}
				ans += leftSame * rightSame;
			} else if (leftSum + rightSum < t) {
				leftIndex++;
			} else {
				rightIndex--;
			}
		}
		System.out.println(ans);
	}
	
}