[DP]백준11084번 가장 쉬운 계단 수

백준10844 가장 쉬운 계단 수

1자리인 경우에 계단 수는 모두 9 개 이다.

맨 앞자리에 0은 올 수 없기 때문이다.

이제 2 자리인 경우부터 그 경우의 수를 따져보면 된다.

우선, 각 경우의 수는 끝자리에 따라 구분할 수 있다.

끝자리가 0 인 경우는 전 자리수에서 끝자리가 1이었던 경우에만 등장할 수 있다.

끝자리가 9 인 경우는 전 자리수에서 끝자리가 8이었던 경우에만 등장할 수 있다.

그 외의 경우는 전 자리수에서 자신보다 하나 작은 것과 하나 큰 것으로부터 올 수 있다.

따라서 다음의 경우들을 dp로 나타내면

if(j >=1 && j <= 8) arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1];
else if(j == 0) arr[i][j] = arr[i-1][j+1];
else if(j==9) arr[i][j] = arr[i-1][j-1];

다음과 같이 된다.

#include <iostream>

using namespace std;

int main(){
    int N;
    cin >> N;
    
    long long arr[101][10];
    for(int i=0;i<10;i++){
        if(i == 0) arr[1][i] = 0;
        else arr[1][i] = 1;
    }
    
    
    for(int i=2;i<=N;i++){
        for(int j=0;j<10;j++){
           if(j >=1 && j <= 8) arr[i][j] = (arr[i-1][j-1] + arr[i-1][j+1]) % 1000000000;
           else if(j == 0) arr[i][j] = arr[i-1][j+1];
           else if(j==9) arr[i][j] = arr[i-1][j-1];
        }
    }
    long long answer = 0;
    for(int i=0;i<10;i++){
        answer += arr[N][i];
    }
    cout << answer%1000000000;
}

문제에서 1,000,000,000으로 나눈 나머지를 저장하고 출력한다고 했기 때문에 나머지만 해주면 된다.

한 가지 놓쳤던 것은, 결과를 출력할 때 다시 한 번 나머지 연산을 해줘야 한다는 것이다.

왜냐하면, 각 숫자들의 경우의 수를 모두 더하는 과정에서 1,000,000,000보다 더 커질 수 있기 때문이다.

이 과정을 빼먹어서 틀렸습니다를 받았다.