백준 2632 (피자판매) - java

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

2632번: 피자판매

 

문제

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

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

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

 

유형 : 누적합

 

접근 방식

• 각 피자를 배열로 봤을 때 중요한 점은 원형 형태라는 것이다.
• 우선 각 배열의 누적합 배열을 구한다.
  • 그리고 각 지점을 기준으로 끝까지 한 방향으로 진행할 때의 구간 값들의 숫자를 count 배열에 추가한다.
• 문제의 핵심은 역순 연산이다. 원형으로 이어져 있을 때 누적합을 구하는 방법은 간단하다.
  • i 지점을 기준으로 첫번 째 원소부터 i 지점의 누적합에 (마지막 인덱스 부터 i + 1 인덱스 지점까지의 구간합니다.)
  • 즉 A[i] + A[n] - A[j] ( j 는 n-1 부터 i + 1 까지 )

 

전체 코드

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

public class BOJ_2632_피자판매 {

    static int des,n,m;
    static int[] A;
    static int[] B;

    static int[] aCount = new int[2_000_001];
    static int[] bCount = new int[2_000_001];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        des = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        A = new int[n+1];
        B = new int[m+1];

        for(int i = 1 ; i <= n ; i++){

            int cur = Integer.parseInt(br.readLine());

            A[i] = A[i-1] + cur;
        }

        for(int j = 1 ; j <= m ; j++){

            int cur = Integer.parseInt(br.readLine());

            B[j] = B[j-1] + cur;
        }

        for(int i = 1 ; i <= n ; i++){
            for(int j = i ; j <= n ; j++){
                int tmpSum = A[j] - A[i-1];
                aCount[tmpSum]++;
            }
        }

        for(int i = 1 ; i <= m ; i++){
            for(int j = i; j <= m ; j++){
                int tmpSum = B[j] - B[i-1];
                bCount[tmpSum]++;
            }
        }

        for(int i = 1 ; i <= n ; i++){
            for(int j = n - 1 ; j >= i + 1; j--){
                int tmpSum = A[i] + A[n] - A[j];
                aCount[tmpSum]++;
            }
        }

        for(int i = 1 ; i <= m ; i++){
            for(int j = m - 1 ; j >= i + 1 ; j--){
                int tmpSum = B[i] + B[m] - B[j];
                bCount[tmpSum]++;
            }
        }

        long result = 0;

        if(des <= 1000_000){
            result += aCount[des] + bCount[des];
        }

        for(int i = 1 ; i < des ; i++){

            if(i > 1000_000 || (des - i) > 1000_000)
                continue;

            result += (aCount[i] * bCount[des - i]);

        }

        System.out.println(result);
        br.close();
    }
}