BOJ 2632 피자판매

https://www.acmicpc.net/problem/2632

문제

고객이 두 종류의 피자 A와 B를 취급하는 피자가게에서 피자를 주문하고자 한다. <그림 1>과 같이 각 종류의 피자는 다양한 크기의 여러 개의 피자조각으로 나누어져 있다. 각 조각에 쓰여진 숫자는 피자조각의 크기를 나타낸다.

<그림 1>

고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다. 이때 판매한 피자조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자조각은 모두 A종류이거나, 모두 B종류이거나, 또는 A와 B 종류가 혼합될 수 있다. 예를 들어서, <그림 1> 과 같이 잘라진 피자가 있을 때, 손님이 전체 크기가 7 인 피자를 주문하면, 피자 가게에서는 <그림2>와 같이 5 가지 방법으로 피자를 판매할 수 있다.

<그림 2>

피자가게에서 손님이 원하는 크기의 피자를 판매하는 모든 방법의 가지 수를 계산하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n ≤ 1000). 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기는 시계방향으로 차례로 주어지며, 각 피자 조각의 크기는 1000 이하의 자연수이다.

---

출력

첫째 줄에는 피자를 판매하는 방법의 가지 수를 나타내는 정수를 출력한다. 피자를 판매하는 방법이 없는 경우에는 숫자 0을 출력한다.

---

예제 입력 1

7
5 3
2
2
1
7
2
6
8
3

예제 출력 1

5

---

코드

처음 문제를 읽고 피자를 원형 링크드 리스트 방식으로 보면 쉽게 풀릴 것 같았다.

풀이 과정은 다음과 같다.

※ 구매 목표 피자 크기는 아래에서 goal로 표현한다.

1. 피자 A, B 각각 연속된 피자 조각들을 잘라 만들 수 있는 크기들의 경우의 수를 구한다.

   sizes[0] = 1, sizes[1] = 5, …, sizes[goal] = 1 과 같이 모든 각각의 크기를 만들 수 있는 경우의 수를 구한다.

2. 피자 A, B로 만들 수 있는 각각의 크기의 수를 곱하여 피자를 판매할 수 있는 경우의 수를 구한다.

   sizesOfA[0] * sizesOfB[goal] + sizesOfA[1] * sizesOfB[goal - 1] + … + sizesOfA[goal] * sizesOfB[0] 과 같이 두 피자의 조각들로 만들 수 있는 크기의 합이 goal인 경우의 수들을 구할 수 있다.

내가 설명을 다 적어놓고 다시 읽어봐도 읽는 사람이 잘 이해가 안 갈 것 같다.

차라리 코드를 천천히 읽어 보는 게 더 빨리 이해할 수 있을 것 같다.

다 풀고 알고리즘 분류를 확인했을 때 이분 탐색이 있었는데, 이분 탐색을 활용한 풀이법은 잘 떠오르지 않는다.

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

public class Main {

    static int goal; // 손님이 구매하고자 하는 피자크기
    static int M;
    static int N;
    static int[] A; // 피자 A 조각들의 크기
    static int[] B; // 피자 B 조각들의 크기

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        goal = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        A = new int[M];
        B = new int[N];
        for (int i = 0; i < M; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }

        for (int i = 0; i < N; i++) {
            B[i] = Integer.parseInt(br.readLine());
        }

        int answer = countCases();

        System.out.println(answer);
    }

    static int countCases() {
        int[] sizesOfA = calculateSizes(A);
        int[] sizesOfB = calculateSizes(B);

        int cases = 0;
        for (int i = 0; i <= goal; i++) {
            cases += sizesOfA[i] * sizesOfB[goal - i];
        }

        return cases;
    }

    /**
     * 연속된 피자 조각을 잘라 만들 수 있는 크기들의 경우의 수를 구하는 메소드
     * @param pizza
     * @return 각 피자 크기들을 만들 수 있는 경우의 수
     * ex) return 된 배열을 sizes 라고 할 때, sizes[5]는 연속된 피자 조각을 잘라 5의 크기를 만들 수 있는 경우의 수
     */
    static int[] calculateSizes(int[] pizza) {
        int[] sizes = new int[goal + 1];
        sizes[0] = 1; // 크기가 0이 되는 경우는 어떠한 피자 조각도 선택하지 않는 한 가지 뿐

        int total = 0;
        for (int i = 0; i < pizza.length; i++) {
            calculateSizesOf(sizes, pizza, i);
            total += pizza[i];
        }

        // 피자 한 판을 모두 더했을 때 구매 목표 크기보다 작으면, 해당 크기의 경우의 수에 1 추가
        if(total <= goal) {
            sizes[total]++;
        }

        return sizes;
    }

    /**
     * 특정 조각을 포함했을 때, 만들어 낼 수 있는 피자 크기들을 계산하는 메소드
     * @param sizes 만들 수 있는 피자 크기의 경우의 수를 세기 위한 배열
     * @param pizza 피자 조각들의 크기 배열
     * @param start 포함할 특정 조각의 인덱스
     */
    static void calculateSizesOf(int[] sizes, int[] pizza, int start) {
        int sum = pizza[start];

        // 포함할 피자 조각의 크기가 구매를 목표로 하는 크기보다 큰 경우, 탐색 종료
        if(sum > goal) {
            return;
        }

        sizes[sum]++;

        // 피자 한 바퀴를 원형 링크드 리스트 방식으로 순회하며 만들 수 있는 피자 크기들을 계산
        int prev = getPrevPiece(pizza, start);
        for (int i = getNextPiece(pizza, start); i != prev; i = getNextPiece(pizza, i)) {
            sum += pizza[i];

            if(sum > goal) {
                break;
            }

            sizes[sum]++;
        }
    }

    // 다음 피자 조각의 인덱스를 반환하는 메소드
    static int getNextPiece(int[] pizza, int current) {
        if(current >= pizza.length - 1) {
            return 0;
        }

        return current + 1;
    }

    // 이전 피자 조각의 인덱스를 반환하는 메소드
    static int getPrevPiece(int[] pizza, int current) {
        if(current <= 0) {
            return pizza.length - 1;
        }

        return current - 1;
    }
}