[백준 10844][C++] 쉬운 계단 수 (Silver 1)

[문제보기]

 10844. 쉬운 계단 수

10844번: 쉬운 계단 수

 

[풀이과정]

이 문제에 대해서 점화식을 세워야되는데, 손으로 계산을 해봤을 때, 자리 수를 의미하는 n은 n-1일 때 수에서 

+1, -1을 1의 자리에 붙는다는 것을 알 수 있다. 

따라서, 이 문제의 점화식은 dp[n][j] = dp[n-1][j-1] + dp[n-1][j+1] 으로 세울 수 있었다.

하지만 j가 0, 9일 때는 한 개의 경우들만 성립 되는데, 0인 경우 01, 012, 0123 ... 으로 1개씩 증가하고, 

9인 경우는 9, 98, 987 ... 으로 1개씩만 증가하게 된다. 

 

필자는 0인 경우 따로 식을 만들었지만, 9인 경우 배열을 하나 더 만들어서 그 부분에는 0값을 넣고, 더해지는 방법을 

사용했다.

 

[소스코드]

#include <iostream>
using namespace std;
long long dp[101][11] = {0};

int main(){
    int n;
    cin >> n;

    for(int i=1; i<10; i++){
        dp[1][i] = 1;
    }

    for(int i=2; i<=n; i++){
        dp[i][0] = dp[i-1][1];
        for(int j=1; j<10; j++){
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
        }
    }

    long long sum = 0;
    for(int i=0; i<10; i++){
        sum += dp[n][i];
    }

    cout << sum % 1000000000;
}

 

[해결 과정 중 실수한 부분]

이 문제에서는 생각해야 되는 부분은 자료형과 1,000,000,000을 나눈 나머지를 생각해줘야되는 부분이다. 

필자는 dp[][]를 더해주는 부분에서는 나누기를 잘했지만, 마지막 sum를 출력하는 부분에서는 1,000,000,000를 

나눠주지를 않아서 틀렸었다.