2011번: 암호코드

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


$O(n)$

dp[0]=1
dp[n]=
(n번째 카드가 1~9일 경우 dp[n-1] 아니면 0)
+(n-1, n번째 카드로 만든 수가 10~26일 경우 dp[n-2] 아니면 0)

#include<cstdio>
int a[5001], dp[5001] = { 1 }, i;
int main() {
    for (i = 1; scanf("%1d", a + i) != -1; i++)
        dp[i] = (dp[i - 1] * (a[i]>0) + dp[i - 2] * (a[i - 1] * 10 + a[i] > 9 && a[i - 1] * 10 + a[i] <= 26)) % 1000000;
    printf("%d", dp[i - 1]);
    return 0;
}