2632번

2632번 - 피자 판매

이전에 풀었던 문제와 비슷하다. 연속된 부분합의 합의 문제라고 할까?

일단 각 피자의 연속된 합을 모두 구하였다. 그래서 sum1 , sum2 배열에 저장하였다.

연속된 합이기 때문에, N제한이 1000 이므로 충분히 담을 수 있다고 생각했다.

그래서 구해진 두 연속된합의 수열을 하나씩 뽑아서 목표로 하는 값이 되도록 하면 됐다.

또한 각 피자 하나에서도 만들 수 있는 값들이 있기 때문에 , 

sum1,sum2 에 0을 추가해줘서 하나의 피자에서도 값이 나올 수 있다면 정답을 체크 하도록 하였다.

###

나는 풀 때 모든 조각을 구하는 makeAll 함수에서 실수가 발생했다.

피자 전체 한판을 구하는게 중복이 되게도 짜는 등 실수를 많이 했다..

구하고자 하는 값이 크면 더 구할 필요가 없이 바로 다음 조각으로 넘어가는 스킬!

완전탐색을 할 때 중요한 부분인 것 같다. 좋은 문제인 것 같다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
vector<int> sum1;
vector<int> sum2;
 
void makeAll(vector<int> pizza, int goal, int k)
{
    int left = 0, right = 0, sum = 0;
    bool first = true;
    while (left != pizza.size())
    {
        sum += pizza[right++];
        if (sum <= goal)
        {
            if (k == 1)
            {
                sum1.push_back(sum);
            }
            else
            {
                sum2.push_back(sum);
            }
        }
        else    //값이 크면 그냥 left 증가
        {
            left++;
            right = left;
            sum = 0;
        }
 
        if (right == pizza.size())
        {
            right = 0;
        }
 
        //피자 한판 전체 값 중복 방지
        if (right == left - 1 || (left==0 && right==0))
        {
            left++;
            right = left;
            sum = 0;
        }
    }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int goal, n, m;
    long long ans = 0;
    scanf("%d%d%d", &goal, &n, &m);
    vector<int> pizza1(n);
    vector<int> pizza2(m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &pizza1[i]);
    }
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &pizza2[i]);
    }
    sum1.push_back(0);
    sum2.push_back(0);
    makeAll(pizza1, goal, 1);
    makeAll(pizza2, goal, 2);
 
    sort(sum1.begin(), sum1.end());
    sort(sum2.begin(), sum2.end());
 
    int i = 0;
    while (i < sum1.size())
    {
        auto l = lower_bound(sum2.begin(), sum2.end(), goal - sum1[i]);
        auto u = upper_bound(sum2.begin(), sum2.end(), goal - sum1[i]);
 
        ans += u - l;
 
        i++;
    }
 
    printf("%lld\n", ans);
 
 
    return 0;
}