백준 #10844. 쉬운 계단 수 (C++)

백준 #10844. 쉬운 계단 수

정리

• bottom-up 방식의 동적 계획법으로 문제를 해결했다. (N을 입력받으면, 길이가 N에 도달할 때까지 0부터(혹은 1부터) 차례대로 길이가 i인 계단 수의 개수를 2차원 배열 dp[101][10]에 저장한다.)
• 2차원 배열인 이유는 끝 자리 숫자가 0~9인 경우를 각각 나눠서 저장해야 하기 때문이다. 예를 들어, 길이가 2이고 끝 자리 수가 1인 계단 수는 dp[2][1]에 저장하고, 여기에 해당하는 값은 dp[1][0] + dp[1][2]이다. 이런 식으로 끝 자리 숫자를 기준으로 각 길이마다 계단 수의 개수를 더해 나가며 길이가 N이 될 때까지 반복한다.
• 이 문제도 결과 값의 나머지를 구해야 하는 문제이다. 모듈러 연산의 분배법칙에 대해 정리해 두고 다시 한 번 복기하자. 모듈러(Modular) 연산의 분배법칙 정리

정답 코드

#include <iostream>

#define MOD 1000000000

using namespace std;

int dp[101][10];
// 길이가 N인 수에 대해, 끝 자리 숫자가 각각 1~9일 때의 계단 수의 개수를 담는 2차원 배열
int res = 0;

int main(void) {
    int N;
    cin>>N;
    
    for(int i=0; i<=9; i++) {
        dp[0][i] = 0;
    }
    // 길이가 0일 때의 값 초기화
    
    dp[1][0] = 0;
    for(int i=1; i<=9; i++) {
        dp[1][i] = 1;
    }
    // 길이가 1일 때의 값 초기화
    
    for(int i=2; i<=N; i++) {
        dp[i][0] = dp[i-1][1];
        // 끝 자리 숫자가 0이려면, 그 전 자리 숫자가 반드시 1이어야 한다.
        for(int j=1; j<9; j++) {
            dp[i][j] = ((dp[i-1][j-1] % MOD) + (dp[i-1][j+1] % MOD)) % MOD;
        }
        dp[i][9] = dp[i-1][8];
        // 끝 자리 숫자가 9이려면, 그 전 자리 숫자가 반드시 8이어야 한다.
    }
    // 길이가 2 이상일 때 처리
    
    for(int i=0; i<=9; i++) {
        res = ((res % MOD) + (dp[N][i] % MOD)) % MOD;
    }
    cout<<res<<endl;
    
    return 0;
}