백준 2632 - 피자판매

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

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

---

 

 

 

 

 

 

풀이

문제를 요약하면, A, B 두 개의 피자에 대한 조각의 크기가 주어진다.

주어진 피자들을 사용하여 목표 크기의 조각을 만들면 된다.

이때, 피자는 연속으로 위치한 피자들만 사용할 수 있다.

 

처음에는 2개의 피자를 모두 검사하는 DP라고 생각했다.

하지만, 피자는 연속으로 있어야 사용이 가능하기 때문에 메모이제이션을 사용하는 것은 문제가 있다.

따라서, 피자를 연속적으로 이용하여 만들 수 있는 조각의 수에 대한 기록이 필요하다.

 

즉, 누적합을 이용하여 만들 수 있는 조각의 경우의 수를 체크한 뒤, 목표로 하는 조각을 다른 조각의 합으로 만들 수 있는지 확인하면 된다.

이때, 같은 피자를 두 번 사용하는 것은 불가능하다.

하나의 피자로 목표 조각 수를 만들 수 있지만, 해당 경우는 누적합에 의해 확인이 되는 경우이다.

또한, 연속된 조각이 아닐 수 있기 때문에 카운팅해서는 안된다.

 

만들 수 있는 조각의 경우의 수를 구하는 방법은 다음과 같다.

하나의 시작점을 정한 뒤, 피자의 크기보다 하나 적게 모든 조각을 더해나가면 된다.

모든 조각을 이용하는 경우는 한 번만 카운팅해야 하기 때문이다.

해당 경우는 입력을 받을 때 처리하면 된다.

int temp = 0;
for (int i = 0; i < M; i++)
{
        cin >> PizzaA[i];
    temp += PizzaA[i];
}
sumA[temp]++;


for (int i = 0; i < M; i++)
{
    int sum = 0;
    for (int j = i; j < i + M - 1; j++)
    {
        sum += PizzaA[j % M];
        sumA[sum]++;
    }
}

 

이후, A피자의 조각의 합과 B피자 조각의 합으로 목표(P)를 만들 수 있는지 확인하면 된다.

그리고 B를 통해서만 목표를 만들 수 있는지 확인하면 된다.

for (auto [a, cnt] : sumA)
{
    int last = P - a;
    if (a == P) ans += cnt;
    else if (sumB[last] != 0) ans += cnt * sumB[last];
}

for (auto [b, cnt] : sumB)
{
    if (b == P) ans += cnt;
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <set>

using namespace std;
vector<pair<int, int>> Teachers;

vector<int> dy = { -1, 0, 1, 0 };
vector<int> dx = { 0, 1, 0, -1 };

bool Check(vector<vector<char>>& School)
{
    for (auto& [y, x] : Teachers)
    {
        for (int i = 0; i < 4; i++)
        {
            int newY = y;
            int newX = x;

            while (true)
            {
                newY += dy[i];
                newX += dx[i];

                if (newY < 0 || newY >= School.size() || newX < 0 || newX >= School.size()) break;
                if (School[newY][newX] == 'O') break;
                if (School[newY][newX] == 'S') return false;
            }
        }
    }

    return true;
}

bool DFS(vector<pair<int, int>>& Obstacles, vector<vector<char>>& School, int depth, int idx)
{
    if (depth == 3)
    {
        return Check(School);
    }

    for (int i = idx; i < Obstacles.size(); i++)
    {
        School[Obstacles[i].first][Obstacles[i].second] = 'O';
        bool bResult = DFS(Obstacles, School, depth + 1, i + 1);
        School[Obstacles[i].first][Obstacles[i].second] = 'X';

        if (bResult) return true;
    }

    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int P, M, N;
    cin >> P >> M >> N;

    vector<int> PizzaA(M);
    vector<int> PizzaB(N);
    map<int, int> sumA;
    map<int, int> sumB;
    int ans = 0;

    {
        int temp = 0;
        for (int i = 0; i < M; i++)
        {
            cin >> PizzaA[i];
            temp += PizzaA[i];
        }
        sumA[temp]++;
    }

    {
        int temp = 0;
        for (int i = 0; i < N; i++)
        {
            cin >> PizzaB[i];
            temp += PizzaB[i];
        }
        sumB[temp]++;
    }


    for (int i = 0; i < M; i++)
    {
        int sum = 0;
        for (int j = i; j < i + M - 1; j++)
        {
            sum += PizzaA[j % M];
            sumA[sum]++;
        }
    }

    for (int i = 0; i < N; i++)
    {
        int sum = 0;
        for (int j = i; j < i + N - 1; j++)
        {
            sum += PizzaB[j % N];
            sumB[sum]++;
        }
    }

    for (auto [a, cnt] : sumA)
    {
        int last = P - a;
        if (a == P) ans += cnt;
        else if (sumB[last] != 0) ans += cnt * sumB[last];
    }

    for (auto [b, cnt] : sumB)
    {
        if (b == P) ans += cnt;
    }

    cout << ans;

    return 0;
}

---