2019 KCPC poster

2019 KCPC 대자보 (신입생 부문 F번 / 일반 부문 B번) 코드 제출 url

다이나믹 프로그래밍 문제입니다. 점화식을 찾아 봅시다.

$ f(a,x)=f(a_1,x+1)+f(a_2,x+2)+f(a_3,x+3) $ 으로 나타낼 수 있습니다.

이때 $ f(a,x) $는 $ x - n $ 의 수열을 알파벳 a로 시작하여 해석할 수 있는 단어의 수입니다.

$ 26 \times 26 = 656 $ 이므로 최대 3자리까지만 비교해보면 됩니다.

#include <bits/stdc++.h>
using namespace std;
const int SZ=300005;
const int MD=1e9+7;
int arr[SZ];
int memo[30][SZ];
int n;
int dp(int bef, int idx){
    if(idx==n+1) return 1;
    if(memo[bef][idx]!=-1) return memo[bef][idx];
    if(arr[idx]==0) return memo[bef][idx]=0;    
    int tot=0;
    for(int i=0;i<3;i++){
        if(idx+i>n) break;
        int xx=0;
        for(int j=0;j<=i;j++){
            xx=xx*10+arr[idx+j];
        }
        if(xx%bef!=0) continue;
        if(xx/bef>26) break;
        tot=(tot+dp(xx/bef,idx+i+1))%MD;
    }
    return memo[bef][idx]=tot;
}
int main(void){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    memset(memo,-1,sizeof(memo));
    int ans=0;
    for(int i=1;i<=26;i++) ans=(ans+dp(i,1))%MD;
    cout<<ans;
    return 0;
}