[BaekJoon] 2632 피자판매 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static int m, n, target;
    static int[] A, B;

    static void input() {
        Reader scanner = new Reader();

        target = scanner.nextInt();
        m = scanner.nextInt();
        n = scanner.nextInt();
        A = new int[m];
        B = new int[n];

        for(int idx = 0; idx < m; idx++)
            A[idx] = scanner.nextInt();

        for(int idx = 0; idx < n; idx++)
            B[idx] = scanner.nextInt();
    }

    static void solution() {
        int[] caseA = makeCaseNum(target, A);
        int[] caseB = makeCaseNum(target, B);

        long answer = (long)(caseA[target] + caseB[target]);
        for(int idx = 1; idx < target; idx++)
            answer += (caseA[idx] * caseB[target - idx]);

        System.out.println(answer);
    }

    static int[] makeCaseNum(int target, int[] sizes) {
        int[] caseNum = new int[target + 1];
        int[] expandedSizes = new int[sizes.length * 2];
        System.arraycopy(sizes, 0, expandedSizes, 0, sizes.length);
        System.arraycopy(sizes, 0, expandedSizes, sizes.length, sizes.length);

        for(int start = 0; start < sizes.length; start++) {
            int sum = 0;
            for(int idx = 0; idx < (start == 0 ? sizes.length : sizes.length - 1); idx++) {
                sum += expandedSizes[start + idx];
                if(sum <= target) caseNum[sum]++;
            }
        }

        return caseNum;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• A와 B 각각에 대해서 나올 수 있는 모든 경우의 수를 우선 계산합니다.
  • A를 기준으로 설명하면, 우선 A의 배열을 반복하여 A의 길이에 2배에 해당하는 배열을 생성합니다.
  • 그리고 각 크기에서 A에 있는 조각으로 만들 수 있는 경우의 수를 나타내는 배열을 하나 생성합니다.
  • 첫 번째 조각부터 마지막 조각까지 순회하면서 모든 경우의 수를 구합니다.
    • 시작 조각부터 (A의 길이 - 1)개의 조각에서 누적합을 구하며 각각의 구해나가는 합이 구매하고자 하는 피자크기보다 작거나 같다면 그 크기에 해당하는 경우의 수를 1씩 증가시킵니다.
    • 그런데 시작 조각이 첫 번째 조각이라면 (A의 길이)개의 조각에서 누적합을 구합니다.
      • 모든 시작 조각에 대해 (A의 길이)개의 조각에서 누적합을 구하면 모든 조각에 대한 합은 (A의 길이)번만큼 나타나기 때문에 중복을 제거하기 위해 시작 조각이 첫 번째 조각일 때만 (A의 길이)개의 조각에서 누적합을 구합니다.
  • 모든 경우의 수를 구했다면 각 크기에서 A에 있는 조각으로 만들 수 있는 경우의 수들을 나타내는 배열을 반환합니다.
• 이렇게 A, B에 대해 모든 경우의 수를 구했다면 답을 나타내는 answer라는 변수를 만들고 각 배열을 caseA, caseB, 구매하고자 하는 피자크기를 target이라고 한다면 caseA[target] + caseB[target]으로 값을 초기화합니다. 이는 A만을 이용하여, 그리고 B만을 이용하여 target만큼 판매하는 경우를 의미합니다.
• 이후에는 1부터 target - 1까지 순회하며 A와 B를 혼합하여 판매하는 경우의 수들을 더해나갑니다.
  • 현재 순회하는 수를 idx라고 한다면, caseA[idx] * caseB[target - idx]를 구하여 이를 answer에 더해나갑니다.