[백준]피자판매(2632)

문제 링크 : [백준]피자판매(2632)

문제 설명

N개의 조각으로 나누어진 피자 A와 M개의 조각으로 나누어진 피자 B가 있습니다.
각각의 조각들의 크기가 시계방향으로 주어졌을 때, 각각의 피자에서 이어진 조각을 하나씩 고르거나, 둘중 하나에서만 하나의 조각을 고르는 경우 중, 크기가 K인 경우의 수를 구하세요.

입력

K(원하는 피자의 크기, 1 <= K <= 2,000,000)
N(A피자의 조각 수, 3 <= N <= 1,000)
M(B피자의 조각 수, 3 <= M <= 1,000)
A_i(A피자 조각의 크기, 1 <= A_i <= 1,000)
B_i(B피자 조각의 크기, 1 <= B_i <= 1,000)

7
5 3
2
2
1
7
2
6
8
3

출력

5

카테고리

#슬라이딩윈도우 #누적합

시간 복잡도 상한

O(N²logN) 혹은 O(M²logM)

해결 방법

1. 각 피자별로 연속된 구간들의 합을 구합니다.
   1-1. 각 피자가 한칸으로 이루어진 경우, 두칸으로 이루어진 경우....
   1-2. 모든 칸에서 시작하는 경우를 모두 구해야합니다.
   1-3. 단 한판 통채인 경우, 하나의 경우만 셉니다.
   1-4. 구간들의 합을 구할 때는, 피자의 연속된 조각의 사이즈를 정해 놓고 슬라이딩 윈도우로 구하면 빠르게 구할 수 있습니다.
   1-4. 각 피자에 크기가 0인 경우를 하나씩 체크해줍니다.(안고를 수도 있기 때문입니다.)
2. 각 경우들을 세면서, 그때의 크기를 카운팅합니다.
3. 최대 크기가 1,000,00이므로 4MB만 있으면 가능합니다.
4. 두 피자에 대해서 각각 카운팅을 했으면, A피자에서 나온 경우의 수를 기준으로 B피자와 합쳐 크기가 K가 되는 경우들을 구합니다.

시간복잡도

O(N² + M²)

코드

#include<cstdio>
int k,n,m,d[1000],e[1000],f[1000001],g[1000001],i,j,x;
long long a;
void s(int e[],int d[],int n){
    for(i=0;i<n-1;i++){
        for(x=j=0;j<=i;j++)x+=d[j];
        e[x]++;
        for(j=1;j<n;j++){
            x-=d[j-1]-d[(j+i)>=n?j+i-n:j+i];
            e[x]++;
        }
    }
    x=0;
    for(i=0;i<n;i++)x+=d[i];
    e[x]++;
}
int main(){
    scanf("%d%d%d",&k,&n,&m);
    for(i=0;i<n;i++)scanf("%d",d+i);
    for(i=0;i<m;i++)scanf("%d",e+i);
    s(f,d,n);s(g,e,m);
    f[0]=g[0]=1;
    for(i=0;i<=k;i++)a+=f[i]*g[k-i];
    printf("%lld",a);
}