[백준 10844] 쉬운 계단 수

0. 제목

• 백준 10844 쉬운 계단 수
• BOJ 10844 쉬운 계단 수
• C++ 10844 쉬운 계단 수

---

1. 문제

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

---

2. 풀이

• DP 방식을 이용하였다.
• dp[i][j]는 i단계에서 값이 j일때 계단 수의 개수를 의미한다.
• 계단 수란 인접한 모든 자리수의 차이가 1이 나는 수이다. 만약 5단계에서 6일때의 계단수를 알고 싶다면 4단계에서 5일때의 계단 수와 4단계에서 7일때의 계단 수를 합하면 된다.
• 주의해야할 점이 있는데, 마지막 수가 0, 9일때는 그 전단계의 수가 각각, 1, 8일때만 가능하다.
• 마지막에 답을 구하기 위해서는 N단계에서의 0일때부터 9일때까지의 계단 수들을 더하면 된다.

---

3. 코드

#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int N;
    int dp[101][10] = {0}; //0으로 초기화 해줘야 함. 다른 수가 섞일 수 있기 때문
    int sum = 0;
    
    cin >> N;
    
    for(int i = 1; i <= 9; i++)
        dp[1][i] = 1;   //1단계에 i일때 쉬운계단의 갯수
    
    for(int i = 2; i <= N; i++){
        dp[i][0] = dp[i-1][1];
        dp[i][9] = dp[i-1][8];
        
        for(int j = 1; j <= 8; j++)
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
    }
    
    for(int i = 0; i < 10; i++){
        sum += dp[N][i];
        sum %= 1000000000;
    }
    cout << sum << '\n';
    return 0;
}