Bin_S+StudyRoom

• 문제

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

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

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

• 입력

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

• 출력

첫째 줄에는 피자를 판매하는 방법의 가지 수를 나타내는 정수를 출력한다. 피자를 판매하는 방법이 없는 경우에는 숫자 0을 출력한다.

• 예제 입력

7
5 3
2
2
1
7
2
6
8
3

• 예제 출력

5

• 접근방식

누적합을 이용해서 푸는데
a에서 만들수 있는 경우의 수, b에서 만들수 있는 경우의 수, a와 b에서 꺼내서 만들수 있는 경우의 수를 더하면 된다.

• 코드

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int wantSize, n, m, a[1004], b[1004], psum_a[2008], psum_b[2008], result;
map<int, int> cnt_a, cnt_b;

void make(int n, int psum[], map<int, int>& cnt)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n + i - 1; j++)
        {
            int sum = psum[j] - psum[j - i];
            cnt[sum]++;
            if (i == n)  break;
        }
    }
    return;
}

int main()
{

    cin >> wantSize >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        psum_a[i] = psum_a[i - 1] + a[i];
    }

    for (int i = n + 1; i <= 2 * n; i++)
    {
        psum_a[i] = psum_a[i - 1] + a[i - n];
    }

    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
        psum_b[i] = psum_b[i - 1] + b[i];
    }

    for (int i = m + 1; i <= 2 * m; i++)
    {
        psum_b[i] = psum_b[i - 1] + b[i - m];
    }

    make(n, psum_a, cnt_a);
    make(m, psum_b, cnt_b);

    for (int i = 1; i < wantSize; i++)
    {
        result += cnt_a[wantSize - i] * cnt_b[i];
    }

    result += cnt_a[wantSize];
    result += cnt_b[wantSize];

    cout << result;

    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/2632