10844번: 쉬운 계단 수

#include<cstdio>

long long num[101][10];

int main()

{

int n;

for (int i = 1; i < 10; ++i)

num[1][i] = 1;

scanf("%d", &n);

for (int i = 2; i <= n; ++i)

for (int j = 0; j < 10; ++j)

{

if (j > 0)

num[i][j] += num[i - 1][j - 1];

if (j < 9)

num[i][j] += num[i - 1][j + 1];

num[i][j] %= 1000000000;

}

long long ans = num[n][0];

for (int i = 1; i < 10; ++i)

ans += num[n][i];

printf("%d", ans % 1000000000);

}