백준 2632번 : 피자판매 (C++)

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

2632번: 피자판매

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int pizza;
    int m,n;
    cin>>pizza>>m>>n;
    int a[m];
    int b[n];
    for(int i=0;i<m;i++)
    {
        cin>>a[i];  
    }
    for(int i=0;i<n;i++)
    {
        cin>>b[i];
    }
    vector<int> apizza;
    vector<int> bpizza;
    int tt=0;
    for(int i=0;i<m;i++)
    {
        if(a[i]<=pizza)
        {
            apizza.push_back(a[i]);
            int j=i+1;
            if(j==m)j=0;
            int sum=a[i];
            while(sum<=pizza && i!=j)
            {
                sum+=a[j];
                if(sum<=pizza)apizza.push_back(sum);
                else break;
                j++;
                if(j==m)j=0;
                if(i==j && tt==1)
                {
                    apizza.pop_back();
                }
                if(i==j && tt==0)
                {
                    tt=1;
                }
            }
        }
    }
    tt=0;
    for(int i=0;i<n;i++)
    {
        if(b[i]<=pizza)
        {
            bpizza.push_back(b[i]);
            int j=i+1;
            if(j==n)j=0;
            int sum=b[i];
            while(sum<=pizza && i!=j)
            {
                sum+=b[j];
                if(sum<=pizza)bpizza.push_back(sum);
                else break;
                j++;
                if(j==n)j=0;
                if(i==j && tt==1)
                {
                    bpizza.pop_back();
                }
                if(i==j && tt==0)
                {
                    tt=1;
                }
            }
        }
    }
    apizza.push_back(0);
    bpizza.push_back(0);
    sort(apizza.begin(),apizza.end());
    sort(bpizza.begin(),bpizza.end());
    int res=0;
    for(int i=0;i<apizza.size();i++)
    {
        res+=upper_bound(bpizza.begin(),bpizza.end(),pizza-apizza[i])- lower_bound(bpizza.begin(),bpizza.end(),pizza-apizza[i]);
    }
    cout<<res;
    return 0;
}

 

풀이

24행부터 50행, 51행부터 77행에서 A, B 피자를 한 종류의 피자를 2조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다는 규칙을 지켜서 자를 수 있는 모든 경우의 수의 잘린 피자의 크기의 합을 벡터에 넣어준다. 원형배열처럼 동작하도록 만들기 위해 31행의 if(j==m)j=0; 등의 코드가 들어간다. 여기서 주의해야 할 점은 한 피자의 모든 조각의 크기를 합친 값이 손님이 구매하고자 하는 피자 크기 보다 작아서 모든 조각을 판매하는 경우에는 1가지 경우이다. (1번 조각부터 n번 조각 까지 자르든 2번부터 3번 4 번 ,,, n번 1번 조각까지 자르든 똑같은 경우이다) 이를 위해서 40~47행의 코드가 필요하다. 

 

 그 후에 하나의 피자에서 구매하고자 하는 피자 크기를 다 채울 수 있는 경우를 처리하기 위해 각각의 벡터에 0을 넣어준다. 오름차순으로 정렬한 뒤 lower_bound와 upper_bound를 사용해서 결괏값을 구해준다. ( 각 함수는 해당 값이 배열에서 처음 등장하는 주소와 해당 값을 초과하는 값이 배열에서 처음 등장하는 주소를 반환하고 이를 이용해서 해당 값이 몇 개 나오는지 알 수 있다) 각 함수의 사용법은 아래 주소에서 확인할 수 있다.

 

https://zz12345.tistory.com/17

백준 10816번 : 숫자 카드 2 (C++) (upper_bound , lower_bound)