2632

피자판매 : https://www.acmicpc.net/problem/2632

 

 

기존 7453에서 배운 방식대로 풀이 했다. https://easy16.tistory.com/372?category=1021081 

 

1. a, b 배열의 입력을 받는다.

2. a,b 배열의 부분합의 배열인 aa,bb를 구한다. ( 기본적인 sliding window 방식으로 size를 늘리며 크기를 계산함.)

각 interation당 개수는 N개이며, window의 size가 N인 경우는 1이된다. 

따라서 부분합 배열의 size는 N*(N-1) +1 이 된다. ( b의 경우 M*(M-1) +1)

부분합을 구하면서 T와 같은 값을 미리 찾고, 최종 결과에 합한다.

 

3. 구해진 부분합 배열을 이용하여 T을 조합할 수 있는 경우를 탐색해준다.

값이 모두 양수인 점을 고려하여 bb배열에서 T보다 큰 경우에 대해 미리 bbp값을 조정한다.

 

 

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

public class Main {

	static int N, M, T;

	static int[] a, b;
	static int[] aa, bb;
	static boolean DBG = false;
	static int answer = 0;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		T = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		a = new int[N];
		b = new int[M];

		for (int i = 0; i < N; i++)
			a[i] = Integer.parseInt(br.readLine());
		for (int i = 0; i < M; i++)
			b[i] = Integer.parseInt(br.readLine());

		aa = new int[N * (N - 1) + 1];
		bb = new int[M * (M - 1) + 1];

		int aCount = 0;
		int bCount = 0;
		int abCount = 0;

		int aaIndex = 0;
		for (int ws = 1; ws <= N; ++ws) {
			int lt = 0, rt = 0, sum = 0;
			while (lt < N) {
				while (rt < ws)
					sum += a[rt++ % N];
				sum += a[rt++ % N];
				sum -= a[lt++ % N];
				aa[aaIndex++] = sum;

				if (sum == T)
					aCount++;

				if (ws == N)
					break;
			}
		}

		int bbIndex = 0;
		for (int ws = 1; ws <= M; ++ws) {
			int lt = 0, rt = 0, sum = 0;
			{
				while (lt < M) {
					while (rt < ws)
						sum += b[rt++ % M];
					sum += b[rt++ % M];
					sum -= b[lt++ % M];
					bb[bbIndex++] = sum;
					if (sum == T)
						bCount++;

					if (ws == M)
						break;

				}
			}
		}

		Arrays.sort(aa);
		Arrays.sort(bb);

		if (DBG) {
			System.out.println("aa:");
			for (int v : aa)
				System.out.print(v + " ");
			System.out.println();
			System.out.println("bb:");
			for (int v : bb)
				System.out.print(v + " ");
			System.out.println();
		}

		int aap = 0, bbp = M * (M - 1);

		while (aap < aa.length && bbp > -1) {

			while (bb[bbp] >= T) {
				bbp--;
			}
			if (DBG)
				System.out.printf("aap:%d bbp: %d\n", aap, bbp);
			int aav = aa[aap], bbv = bb[bbp];
			int sum = aav + bbv;

			if (sum < T) {
				aap++;
			} else if (sum > T) {
				bbp--;
			} else {
				int ac = 0, bc = 0;
				while (bbp > -1 && bbv == bb[bbp]) {
					bc++;
					bbp--;
				}
				while (aap < N * (N - 1) + 1 && aav == aa[aap]) {
					ac++;
					aap++;
				}
				abCount += ac * bc;
			}
		}
		if (DBG)
			System.out.printf("ac:%d bc: %d abc :%d\n", aCount, bCount, abCount);
		System.out.println(aCount + bCount + abCount);

	}

}

 

 

다른 방식의 풀이 : https://moonsbeen.tistory.com/308

 

기존 풀이 방식외에 dfs로 계산하는 해법을 찾았다.

위의 포스팅에서 부분합 배열을 정의 하는 방법을 참고하자

 

a_count[ a배열의 부분합 ] 의 의미

 

피자의 한 요소를 i라 하면, sum은 j거리에 떨어진 피자와의 합을 누적한 값.

두번째 for문을 돌 때마다,  i요소의 모든 거리에 있는 값을 합하면서 a_count[sum] 값을 증가시킴.

 

즉, a_count[sum] 는 부분합이 sum이되는 모든 경우의 수가 된다.

    public static void count(int[] pizza, int[] count, int size) {
        for(int i = 0; i < pizza.length; i++) { //시작하는 피자의 인덱스
            int sum = 0;
            for(int j = 1; j < pizza.length; j++) { //선택하는 피자 조각의 개수
                int sum_j = pizza[(i + j) % pizza.length];
                if(sum + sum_j > size) break;
                sum += sum_j;
                count[sum]++;
            }
        }
    }

 

같은 방식으로 b_count를 구한 뒤, a_size + b_size의 값이 T가 되는 경우를 각각 곱한뒤 누적한 값이 답이된다.

(각 sum이 나온 경우마다 1:1대응이 가능하기 때문)

      int result = 0;
        for(int i = 0; i <= size; i++) {
            result += (a_count[i] * b_count[size - i]);
        }
        System.out.println(result);