#백준_2632 피자판매 - Java

# 유형 : 투 포인터

# 피자개수가 최대 1000개라서, N^2로 해도 시간 초과 안나고 시간 제한에서 좀 자유롭다. 따라서 N^2으로 각 피자 조각의 합을 구한다. 이 때 조건문만 잘 지키면 어렵지 않다. 조각의 합을 구하는 조건 틀린부분을 못찾아서 한참을 생각하고 생각하였음. 조각의 합을 구하면 그 이후는 투포인터를 이용해서 구하면 됨. 이 때 투포인터 알고리즘은 A,B각각의 합으로 주어진 피자의 크기를 포함하지 않으므로 반복문을 한번씩 돌려 추가로 체크하면 된다.

package bj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class p2632 {
	static int N,A,B;
	static int A_[],B_[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		
		A_ = new int[A];
		B_ = new int[B];
		
		for(int i=0; i<A; i++) {
			A_[i] = Integer.parseInt(br.readLine());
		}
		for(int i=0; i<B; i++) {
			B_[i] = Integer.parseInt(br.readLine());
		}
		
		ArrayList arr_A = new ArrayList<>();
		ArrayList arr_B = new ArrayList<>();
		int low=0;
		int high=0;
		int sum=0;
		
		while(low<A_.length) {
			sum += A_[high];
			high++;
			
			if(sum<=N) {
				arr_A.add(sum);
			}else {
				low++;
				high = low;
				sum=0;
			}
			
			high%=A;
			
			
			if((low==0 && high==0) || high+1== low) {
				low++;
				high = low;
				sum = 0;
			}
		}
		
		low=0; high=0; sum=0;
		while(low<B_.length) {
			sum += B_[high];
			high++;
			
			if(sum<=N) {
				arr_B.add(sum);
			}else {
				low++;
				high = low;
				sum = 0;
			}
			
			high%=B;
			
			if((low==0 && high==0) || high+1== low) {
				low++;
				high = low;
				sum = 0;
			}
		}
		
		Collections.sort(arr_A);
		Collections.sort(arr_B);
		
		int result=0;
		int left = 0;
		int right = arr_B.size()-1;
		
		while(left<arr_A.size() && right>=0) {
			int left_val = arr_A.get(left);
			int right_val = arr_B.get(right);
			
			if(left_val + right_val == N) {
				int left_cnt=0;
				while(left<arr_A.size() && arr_A.get(left)==left_val) {
					left_cnt++;
					left++;
				}
				int right_cnt=0;
				while(right>=0 && arr_B.get(right) == right_val) {
					right_cnt++;
					right--;
				}
				result += left_cnt*right_cnt;
			}
			
			if(left_val+right_val < N) {
				left++;
			}
			if(left_val+right_val > N) {
				right--;
			}
		}
		for(int i=0; i<arr_A.size(); i++) {
			if(arr_A.get(i) == N)
				result++;
		}
		for(int i=0; i<arr_B.size(); i++) {
			if(arr_B.get(i) == N)
				result++;
		}
		
		System.out.println(result);
	}
}