[백준 10844번] [동적 계획법] 쉬운 계단 수

Approach

완전 탐색 기법으로 해당 문제를 푸는 식으로 문제를 접근해보면, 길이가 N - 1인 계단수의 정보를 활용해서 길이가 N인 계단수를 구할 수 있다는 점을 쉽게 파악할 수 있다.

다만, 마지막 수가 1 ~ 8인지 0이나 9인지 여부에 따라서 경향성이 달라지므로 끝나는 숫자에 대한 정보가 필요한데 이를 dp에 저장해두면 쉽게 풀 수 있다.

 

Let dp[i][j] : 마지막 수가 j이면서 길이가 i인 계단 수 (dp[1][0] = 0, dp[1][1 ~9] = 1 : Initial value)

dp[i][j] : dp[i - 1][j - 1] + dp[i - 1][j + 1] for j $\in$ {2, 3, 4, 5, 6, 7, 8, 9}

dp[i]j] : dp[i - 1][j + 1] for j = 0

dp[i][j] : dp[i - 1][j - 1] for j = 9

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int dp[101][10];
int n;

int memoi(int x, int k){
    if(x == 0) return 0; // Base case
    if(k < 0 || k > 9) return 0;
    int& ret = dp[x][k];
    if(x == 1){
        if(k == 0) return ret = 0;
        else return ret = 1;
    }
    if(ret != -1) return ret;
    return ret = (memoi(x - 1, k - 1) + memoi(x - 1, k + 1)) % 1000000000;
}

int main(void){
    fastio;
    memset(dp, -1, sizeof(dp));
    cin >> n;

    int result = 0;
    for(int i = 0; i < 10; i++){
        result = (memoi(n, i) + result) % 1000000000;
    }
    cout << result << "\n";
    return 0;
}