[백준] 쉬운 계단 수 10844번 (c++)

출처 : 10844번: 쉬운 계단 수 (acmicpc.net)

10844번: 쉬운 계단 수

풀이 방법

계단 수는 +1 또는 -1 차이가 난다.

dp[i][j]를 i자리 수 이면서 j로 시작하는 수로 잡는다

그러면 dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1] 이 된다

주의할 점은 j가 0이면 1로 시작하는 수만 와야하고 j가 9면 8로 시작 한느 수만 올 수 있어

예외 처리를 해주면 된다.

 

//11057
#include <bits/stdc++.h>
using namespace std ;
int n;
vector<int> num;
long long dp[101][10];
long long ans = 0;

void solve() {
    for (int i = 2;i < n + 1;i++) {
        for (int j = 1;j < 9;j++) {
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
        }
        dp[i][0] = dp[i-1][1] % 1000000000;
        dp[i][9] = dp[i-1][8] % 1000000000;
    }
}
int main () {
    memset(dp, 0, sizeof(dp));
    for (int i = 0;i < 10;i++) {
        dp[1][i] = 1;
    }
    cin >> n;
    solve();
    for (int i = 1;i < 10;i++) {
        ans += dp[n][i] ;
    }
    cout << ans % 1000000000 << endl;
    return 0;
}