[백준 10844] 쉬운 계단 수

[ghdcksgml1]

DP만 하면 알고리즘이 하기 싫어지네;;

아이디어

숫자가 0일때는 그다음 계단수가 1밖에 안나오고, 숫자가 9일때는 그다음 계단수가 8밖에 안되기 때문에 1~8 구간과 다른 처리를 해줘야한다.

그래서 다음 계단수가 0일때의 개수는 현재 계단수의 1값을, 다음 계단수가 9일때에는 현재 계단수의 8값을 넣었고,

다음 계단수가 1~8 구간일때에는 가려고 하는 계단수를 A라고 했을때, 현재 계단수 A-1, A+1을 더한 값을 넣어준다.

시간복잡도

O(100 * 10)

소스코드

// 언어 : C++ , (성공/실패) : 1/0 , 메모리 : 2028 KB , 시간 : 0ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h> // memset
#define MOD 1000000000

using namespace std;
typedef long long ll;
ll dp[101][10];

int main(void){
    // 입출력 속도 최적화
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ll N; cin>>N;

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

    for(int i=2;i<=N;i++){
        for(int j=0;j<10;j++){
            if(j==0){
                dp[i][j] = dp[i-1][j+1];
            }else if(j==9){
                dp[i][j] = dp[i-1][j-1];
            }else{
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
            }
            dp[i][j] %= MOD;
        }
    }

    for(int i=0;i<10;i++){
        result += dp[N][i];
        result %= MOD;
    }

    cout<<result<<'\n';

    return 0;
}

[BanApp]

dp문제는 그저 아이디어 싸움..