백준 2632번 피자 판매

접근방법

 

문제에서 고려했던 부분

• 피자 조각의 크기는 크기순으로 주어지지 않음
• 2조각 이상 판매할 때, 피자조각이 연속되어야 함( -> 슬라이딩 윈도우?)

연속되어야 한다는 부분에서 슬라이딩 윈도우 알고리즘을 떠올렸습니다.

 

그리고 경우의 수를 3가지로 나누어보면 아래와 같다.

1. 모두 피자 A인 경우
2. 모두 피자 B인 경우
3. 피자 A와 피자 B 혼합인 경우

그래서 3가지 경우의 수 구한 뒤, 더해주면 되겠다고 생각을 했다.

그리고 3번째 경우인 '피자 A와 피자 B 혼합인 경우'는 (A 경우의 수 *  B 경우의 수) 이다.

 

어려웠던 부분

 

어려웠던 부분은 연속된 숫자들로 만들 수 있는 합을 구하는 것이었다. 피자가 마지막 조각에서 다시 첫번째 조각을 선택할 수도 있었기 때문에 나머지 연산(%)도 고려해야 한다고 생각했다.

 

하지만, 슬라이딩 윈도우를 어떻게 적용할지 고민하다가 고객이 원하는 피자의 크기보다 작다면 윈도우의 크기를 늘리고 고객이 원하는 피자의 크기보다 크다면 윈도우의 크기를 줄이는 방법을 생각했다.
이 방법을 생각했을때 원형큐를 한바퀴 돌고 난 후, 윈도우의 중복여부를 판단할 수 없겠다는 생각이 들었다.

 

구현하는데에 어려움이 있어 다른 풀이를 참고했는데 누적합을 사용해서 푼 것을 확인할 수 있었다.

// 피자A로만 판매하는 경우의 수
int[] sumA = new int[1_000_001];
// 1개부터 M-1개
for (int i = 0; i < M; i++) {
    int sum = 0;
    for (int j = i; j < i+M-1; j++) {
        sum += sizeA[j%M];
        sumA[sum]++;
    }
}

• 여기서 i는 배열에서의 시작점을 의미하고 j는 숫자의 개수를 의미한다. 그리고 원형큐이기 때문에 j%(피자 조각의 개수) 연산으로 큐를 한바퀴 돌고난 후의 인덱스를 구해준다. 그리고 sum을 구할때마다 sumA 배열에 개수를 1씩 증가시켜준다.

고객이 원하는 피자의 크기를 넘지 않게 부분합을 구하지 않고 구할 수 있는 모든 부분합을 구하는게 구현을 단순화 했다.

구현

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

public class Solution_for_2632 {
    static int pizzaSize;
    static int M, N;

    static int[] sizeA;
    static int[] sizeB;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        pizzaSize = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        
        M = Integer.parseInt(st.nextToken());
        sizeA = new int[M];
        
        N = Integer.parseInt(st.nextToken());
        sizeB = new int[N];
        
        int totalA = 0;
        for (int m = 0; m < M; m++) {
            int size = Integer.parseInt(br.readLine());
            sizeA[m] = size;
            totalA += size;
        }

        int totalB = 0;
        for (int n = 0; n < N; n++) {
            int size = Integer.parseInt(br.readLine());
            sizeB[n] = size;
            totalB += size;
        }

        // 피자A로만 판매하는 경우의 수
        int[] sumA = new int[1_000_001];
        // 1개부터 M-1개
        for (int i = 0; i < M; i++) {
            int sum = 0;
            for (int j = i; j < i+M-1; j++) {
                sum += sizeA[j%M];
                sumA[sum]++;
            }
        }
        sumA[totalA]++;

        // 피자B로만 판매하는 경우의 수
        int[] sumB = new int[1_000_001];
        for (int i = 0; i < N; i++) {
            int sum = 0;
            for (int j = i; j < i+N-1; j++) {
                sum += sizeB[j%N];
                sumB[sum]++;
            }
        }
        sumB[totalB]++;

        // 피자A와 피자B를 혼합해서 판매하는 경우의 수
        int answer = 0;
        answer = sumA[pizzaSize];
        answer += sumB[pizzaSize];

        for (int i = 1; i < pizzaSize; i++) {
            answer += (sumA[i] * sumB[pizzaSize-i]);
        }

        System.out.println(answer);
    }
}