2632. 피자판매

INFO

• 링크: 문제 보러가기
• 언어: Java
• 난이도: 2
• 알고리즘: 누적합
• 소요 시간:

1. 문제 이해

핵심 요구사항

• 여러 조각으로 나뉜 피자 A,B를 가지고 손님이 원하는 양을 판매
• 한 피자에서 2조각 이상을 파는 경우 연결해서 팔아야함.
• 목표: 판매하는 모든 방법의 가지 수 || 0

제한 조건

• 변수 범위
  • 구매할 크기 ⇐ 2,000,000
  • 3 ≤ m, n (조각 개수) ≤ 1000
  • 1 ≤ (조각 크기) ≤ 1000
• 시간: 2초
• 메모리: 128MB

2. 사고의 흐름 (Thinking)

• ❌ 1차 접근: 완전 탐색 (Brute Force)

  • 각 피자마다 가능한 조합을 구하고, 하나씩 다 확인해보는 방법.
  • 그러나 조각의 개수 m, n이 각각 최대 1,000이라
    • 피자 A의 조합 구하기 (= 경계선 2개 고르기) = 최악의 경우 $\left(\genfrac{}{}{0ex}{}{1000}{2}\right)\approx 500,000$
    • 피자 B의 조합 구하기 (= 경계선 2개 고르기) = 최악의 경우 $\left(\genfrac{}{}{0ex}{}{1000}{2}\right)\approx 500,000$
    • A에서 하나 B에서 하나씩 고르기 = $500,000\times 500,000$
  • 시간복잡도는 $O(m^2\times n^2)$으로 100% 시간 초과

• ✅ 2차 시도: 구간합

  • 문제에서 말하는 중요한 조건은 피자 사이즈이다
  • 따라서,
    • 조합에 포함되는 조각을 저장하는 것이 아니라, 해당 조합으로 나오는 피자 크기를 저장하기.
    • 구해야하는 피자 사이즈가 S일 때, 피자 A에서 도출된 구간합 a에 대하여 피자 B에서 S-a인 값의 개수를 찾으면 됨.

• ✅ 3차 시도: 구간합 + Map 혹은 counting 배열

  • 더하여 구간의 피자 크기 key 또는 index로이고 그 크기가 등장하는 가짓 수를 value로 하는 자료구조를 사용 → 탐색 속도 줄임.

3. 풀이 및 코드 (Solution)

import java.io.*;  
  
public class BOJ2632_피자판매 {  
    static int order, M,N;  
    static int[] pizza_m;  
    static int[] pizza_n;  
    static int[] size_cnt_m = new int[2000001];  
    static int[] size_cnt_n = new int[2000001];  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        order = Integer.parseInt(br.readLine());  
        String[] temp = br.readLine().split(" ");  
        M = Integer.parseInt(temp[0]);  
        N = Integer.parseInt(temp[1]);  
  
        pizza_m = new int[M];  
        pizza_n = new int[N];  
        size_cnt_m[0] = 1;  
        size_cnt_n[0] = 1;  
  
        // 입력 받기 / 전체 합 구하기  
        int all_m=0, all_n=0;  
        for (int i = 0; i<M; i++) {  
            pizza_m[i] = Integer.parseInt(br.readLine());  
            all_m += pizza_m[i];  
        }  
  
        for (int i = 0; i<N; i++) {  
            pizza_n[i] = Integer.parseInt(br.readLine());  
            all_n += pizza_n[i];  
        }  
  
        // 가능한 조합의 합 구하기  
        if (all_m <= order) size_cnt_m[all_m] = 1;  
        if (all_n <= order) size_cnt_n[all_n] = 1;  
        prefix_sum(pizza_m, size_cnt_m, M);  
        prefix_sum(pizza_n, size_cnt_n, N);  
  
        long result = 0; // 가짓수 구하는 문제는 long이 안전하다고함...  
        for (int size = 0; size <= order; size++) {  
            if (size_cnt_n[size] > 0) {  
                result += (long) size_cnt_n[size]*size_cnt_m[order-size];  
            }  
        }  
        System.out.println(result);  
    }  
  
    static void prefix_sum(int[] piece, int[] sum_cnt, int len) {  
        // 조각이 2 ~ m-1(n-1) 개 일때 크기 저장  
        int sum;  
        for (int start = 0; start < len; start++) {  
            sum = 0;  
            for (int end = start; end < len+start-1; end++) {  
                sum += piece[end%len];  
                if (sum <= order) sum_cnt[sum]++;  
                else break;  
            }  
        }  
    }  
}

• 구간합은 누적합을 사용하여 구하였음.

• 시간 복잡도: $O(N^2)$ → 부분합을 구하는 곳에서 이중 for문 사용

4. 회고 (Retrospective)

• 이번에도, 중요한 조건에 집중하는 습관이 필요했음.
• 누적합으로 구간합을 구하는 것도 알고 있었는데, 오래간만이라 이상하고 복잡하게 누적합을 구함ㅋㅋㅋㅋ → 문제 더 많이 풀자자

Computer PS