2591번: 숫자카드

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


$O(n)$

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

#include<cstdio>
int a[41], dp[41] = { 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] <= 34);
    printf("%d", dp[i - 1]);
    return 0;
}