백준 10844 - 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

고려사항

- memo[len][num] 은 len 길이의 수 중 끝이 num 으로 끝나는 수의 개수.

- 끝 수가 0과 9일 때는 각각 길이가 1 짧은 수들 중 끝이 1, 8 로 끝나는 수의 개수이며

이 밖에는 길이가 1 짧은 수들 중 끝이 자신과 1 차이나는 수로 끝나는 수의 개수들을 더한다.

- memo[len][num] = memo[len-1][num+1] + memo[len-1][num-1]

- 계산 후 % 10억

- 스위치문을 썼는데 모든 끝 자리수를 탐방하니 0~9까지 반복문을 활용하면 더욱 코드를 깨끗하게 쓸 수 있을 꺼 같다..

 

#include <iostream>
#include <string.h>
using namespace std;
 
int n;
int memo[101][11];
 
int dp(int len, int num){
    int &v = memo[len][num];
 
    if(len <= 1){
        return v;
    }
 
    if(len == 2){
        switch (num) {
            case 0:
                v = 1;
                break;
            case 1:
                v = 1;
                break;
            case 9:
                v = 1;
                break;
            default:
                v = 2;
                break;
        }
        return v;
    }
 
    if(v != -1){
        return v;
    }
 
    switch (num) {
        case 0:
            v = dp(len-1,1);
            break;
        case 1:
            v = dp(len-1,0)+dp(len-1,2);
            break;
        case 2:
            v = dp(len-1,1)+dp(len-1,3);
            break;
        case 3:
            v = dp(len-1,2)+dp(len-1,4);
            break;
        case 4:
            v = dp(len-1,3)+dp(len-1,5);
            break;
        case 5:
            v = dp(len-1,4)+dp(len-1,6);
            break;
        case 6:
            v = dp(len-1,5)+dp(len-1,7);
            break;
        case 7:
            v = dp(len-1,6)+dp(len-1,8);
            break;
        case 8:
            v = dp(len-1,7)+dp(len-1,9);
            break;
        case 9:
            v = dp(len-1,8);
            break;
    }
 
    v %= 1000000000;
    return v;
}
 
int main() {
    cin>>n;
    int ans = 0;
 
    memset(memo,-1,101*11*4);
    memo[0][0] = 0;
    memo[1][0] = 0;
    for(int i=1;i<10;++i){
        memo[0][i] = 0;
        memo[1][i] = 1;
    }
 
    for(int i=0;i<10;++i){
        ans += dp(n,i);
        ans %= 1000000000;
    }
 
    cout<<ans;
    return 0;
}