[백준OJ] 10844번 쉬운 계단 수

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

10844번: 쉬운 계단 수

---

 

-풀이-

dp[i][j] = k 라고할때, 길이가 i인 수중, 마지막 숫자가 j인 계단 수의 개수가 k라고 하자.

 

일단,1자리 일때의 계단수는 몇개일까?

마지막 숫자가 1인 계단수는 1개, 

2인 계단수는 1개,

3인 계단수는 1개,

...

9인 계단수는 1개이다.

0으로 시작하는 수는 없으므로, 1자리일때의 계단수는 0을 제외하고 모두 1개이다.

 

그럼 2자리일때 계단수는 몇개일까?

먼저 마지막 숫자가 0인 계단수가 되려면 , 길이가 1인 경우중, 마지막 숫자가 1인 경우에서 뒤에 0만 붙여주면 완성이 되므로, dp[1][1]이 된다. 

맨 뒷자리가 1인 계단수가 되려면, 1자리일때 맨 뒷자리가 0인 경우와 2인 경우에 뒷자리에 1을 붙여줄 때, 길이가 2면서 맨뒷자리가 1인 계단수가 완성이 되므로 dp[1][0]+dp[1][2]가 된다.

규칙을 찾았는가?

j==0일땐 dp[i][0]=dp[i-1][1] 이 성립하고,

j!=0 일땐, dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1] 이 성립하므로, 이 점화식을 써서 N자리수일때, 마지막 숫자가 0~9인 경우를 모두 더해서 출력해주면 된다.

 

-시간복잡도-

O(N)

 

-코드-

#include <algorithm>
#include<iostream>
#define MOD 1000000000

using namespace std;


long long dp[101][11]={0};

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=9;i++) dp[1][i]=1;
    
    for(int i=2;i<=n;i++){
        dp[i][0]=dp[i-1][1];
        for(int j=1;j<=9;j++){
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%MOD;
        }
    }
    long long sum=0;
    for(int i=0;i<=9;i++){
        sum+=dp[n][i];
    }
    cout<<sum%MOD<<"\n";
}