[백준] 2632 피자판매

이 문제는 lower_bound && upper_bound를 이용하여 풀었다

반드시 연속적인 부분을 잘라야하고 피자가 원이라는 것을 잘 생각해야한다!

그럼 원에서 연속적인 부분들의 값을 각 피자의 배열을 만들어 넣고

lower_bound와 upper_bound를 이용해 각 피자에서 나올 수 있는

값과 수를 찾아서  곱하면 답이된다

코드에서는 원이기때문에 1~n이 아닌 1~2n까지 배열을 잡고

맨 뒤어서부터 시작해 만들 수 있는 값도 배열 넣었다

그리고 0과 sum[1~n]값은 한번만 나올 수 있으므로 마지막에 따로 넣어주었다

값을 다 넣고 크기가 P인 피자를 만들때

A에서 i를 찾고 B에서 P-i를 찾은 후 곱해주며 다 더하며 답이다!

 

소스코드

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
int P,n,m;
int A[1010],B[1010],PA[3010],PB[3010];
vector<int> a,b;
int main(){
    //freopen("input.txt","r",stdin);
    scanf("%d %d %d",&P,&n,&m);
    for(int i=1;i<=n;i++) scanf(" %d",&A[i]);
    for(int i=1;i<=m;i++) scanf(" %d",&B[i]);
    for(int i=1;i<=n;i++) PA[i]=PA[i-1]+A[i]; for(int i=n+1;i<=n*2;i++) PA[i]=PA[i-n]+PA[n];
    for(int i=1;i<=m;i++) PB[i]=PB[i-1]+B[i]; for(int i=m+1;i<=m*2;i++) PB[i]=PB[i-m]+PB[m];
    for(int i=1;i<=n;i++){
        for(int j=i;j<i+n-1;j++){
            a.push_back(PA[j]-PA[i-1]);
        }
    } 
    for(int i=1;i<=m;i++){
        for(int j=i;j<i+m-1;j++){   
            b.push_back(PB[j]-PB[i-1]);
        }
    }
    a.push_back(PA[n]); b.push_back(PB[m]);
    a.push_back(0); b.push_back(0);
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int ans=0;
    for(int i=0;i<=P;i++){
        int c = upper_bound(a.begin(),a.end(),i) - lower_bound(a.begin(),a.end(),i);
        int w = upper_bound(b.begin(),b.end(),P-i) - lower_bound(b.begin(),b.end(),P-i);         
        if(c&&w) ans+=(c*w);
    }
    printf("%d\n",ans);
}