10844번: 쉬운 계단 수

dp문제다.

0, 9 는 퍼져나갈 수 있는 1과 8밖에 못받고

나머지는 자신의 수 -1, +1인 수의 개수를 받을 수 있다는 것을 이용했다.

처음에 0이 오면 안되기 때문에 마지막에서부터 연산을 진행해 최종적으로

1~9로 시작할 수 있는 계단 수를 더해서 답을 구한다.

(아래의 식을 이용하면 sum이 아닌 dp만을 나누어 준다는 것에 주의!

sum += dp[len-1][k] % 1000000000;)

 

#include <iostream>
 
int main(void) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int len;
    std::cin >> len;
 
    long long dp[101][10] = { 0 };
    for(int i = 0; i < 10; i++) {
        dp[0][i] = 1;
    }
 
    for(int i = 1; i < len; i++) {
        for (int j = 0; j < 10; ++j) {
            if (j == 0 && i < len - 1) {
                dp[i][j] = dp[i - 1][j + 1];
            } else if (j == 9) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] % 1000000000;
            }
        }
    }
    
    long long sum = 0;
    for (int k = 1; k < 10; ++k) {
        sum = (sum + dp[len - 1][k]) % 1000000000;
    }
 
    std::cout << sum << "\n";
    return 0;
}