백준 : 2632 피자판매

www.acmicpc.net/problem/2632

2632번: 피자판매

부분합을 구하는 문제인데 순환된 구간의 부분합을 구하는 문제이다.

단순히 sum에 대한 카운팅하는 문제이지만 원형큐 자료구조로 구하기가 까다로워보인다

 

이럴때는 배열의 크기를 두배로 늘리자

 

[1,7,7,2,4]의 배열을 [1,7,7,2,4,1,7,7,2,4] 의 배열로 만든다음

i~j 합을 구하며된다 그때는 초반크기 5의 기준으로 구한다. 주의할점은 i~ i+전체크기 구간의 sum은 모드 같은 구간의 합인걸 주의하자~

이게 무슨 말이냐.

 

위 배열로 예를들면

 

[1,7,7,2,4] == [7,7,2,4,1] == [7,2,4,1,7] 은 모두 같은 구같의 합이다 이때 카운팅을 잘생각해서 해주면된다.

 

 

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B2632 {
	static int N;
	static int m, n;
	static int a[];
	static int b[];
	static int sumA[] = new int[2000001];
	static int sumB[] = new int[2000001];

	public static void main(String[] args) throws NumberFormatException, IOException {
		init();
		System.out.println(Solve());
	}

	private static int Solve() {
		int answer = 0;
		funSumCnt(m, a, sumA);
		funSumCnt(n, b, sumB);
		for (int i = 0; i <= N; i++) {
			answer += sumA[i] * sumB[N - i];
		}

		return answer;
	}

	private static void funSumCnt(int c, int[] arr, int[] sumCnt) {
		for (int i = 0; i < c; i++) {
			int sum = 0;
			for (int j = i; j < i + c - 1; j++) {
				sum += arr[j];
				sumCnt[sum]++;
			}
		}
	}

	private static void init() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		String[] str = br.readLine().split(" ");

		m = Integer.parseInt(str[0]);
		n = Integer.parseInt(str[1]);

		a = new int[m * 2];
		b = new int[n * 2];

		int sum = 0;
		for (int i = 0; i < m; i++) {
			a[i] = Integer.parseInt(br.readLine());
			a[i + m] = a[i];
			sum += a[i];
		}
		sumA[sum] = 1;
		sumA[0] = 1;

		sum = 0;
		for (int i = 0; i < n; i++) {
			b[i] = Integer.parseInt(br.readLine());
			b[i + n] = b[i];
			sum += b[i];
		}
		sumB[sum] = 1;
		sumB[0] = 1;
	}
}