[BOJ] 2632 : 피자판매

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

---

누적합

[ 알고리즘풀이 ]

 문제 Input 크기를 유심히 들여다보면 쉽게 해결할 수 있는 문제다.

 최대 피자 조각이 1000개이므로 우리는 피자 조각이 연속된 합을 모두 구해보아도 O(N^2) 으로 시간 초과에 걸리지 않는다. 또한, 피자 조각의 크기가 최대 1000이므로 연속된 합이 1000 * 1000 을 넘어가지 않으므로, 10^6 크기의 int 배열로 가능한 모든 피자 조각의 연속된 합을 count 할 수 있다.

 A / B 피자별로 가능한 모든 피자 조각의 연속된 합을 count 하고 난 후, client 가 원하는 크기를 A와 B 피자에서 조각을 꺼내와 만들면 답을 쉽게 구할 수 있다.

 

[ 코드 C++ ]

#include<iostream>
 
using namespace std;
 
int client, nA, nB;
int pizzaA[1000], pizzaB[1000]; // pizza 조각들
int sizeA[1000001] = {}, sizeB[1000001] = {}; // pizza 조각으로 만들 수 있는 크기 count
int ans = 0;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> client >> nA >> nB;
    for (int i = 0; i < nA; i++)
        cin >> pizzaA[i];
    for (int i = 0; i < nB; i++)
        cin >> pizzaB[i];
 
    sizeA[0] = 1, sizeB[0] = 1; 
    int sum = 0;
    for (int i = 0; i < nA; i++)
        sum += pizzaA[i];
    sizeA[sum]++;
    sum = 0;
    for (int i = 0; i < nB; i++)
        sum += pizzaB[i];
    sizeB[sum]++;
 
    for (int i = 0; i < nA; i++) {
        int sum = 0;
        for (int j = 0; j < nA - 1; j++) {
            sum += pizzaA[(i + j) % nA];
            sizeA[sum]++;
        }
    }
    for (int i = 0; i < nB; i++) {
        int sum = 0;
        for (int j = 0; j < nB - 1; j++) {
            sum += pizzaB[(i + j) % nB];
            sizeB[sum]++;
        }
    }
    // client 가 원하는 조각을 몇 개 만들 수 있는지 count 해준다.
    for (int i = 0; i <= client; i++)
        ans += (sizeA[i] * sizeB[client - i]);
 
    cout << ans << '\n';
}

[ github ]

https://github.com/travelbeeee/BOJ/blob/master/BOJ2632.cpp

travelbeeee/BOJ

---