[백준] 10844. 쉬운 계단 수

 

[문제]

 

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

[풀이]

 

DP 배열을 2차원을 선언하여 풀었다.

DP[i][j]는 i자리 수에서 마지막 숫자가 J인 경우의 수를 나타낸다.

예를 들어 DP[2][2]는 'X2'인 경우로 12,32가 있으므로 2이다.

따라서 계단 수를 구하는 것이므로 점화식을 아래와 같이 세울 수 있다.

DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1];

단 , j가 0이거나 9인 경우 따로 예외처리 해줘야된다.

 

[코드]

 

#include <iostream>
#define MAX 101
#define MOD 1000000000

using namespace std;

int DP[MAX][10]={0,};

int main(void)
{
    int N;
    
    cin >> N;

    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][1]%MOD;
            else if(j==9)   DP[i][j] = DP[i-1][8]%MOD;
            else DP[i][j]= (DP[i-1][j-1] + DP[i-1][j+1])%MOD;
        }
    }
    
    int sum =0;
    for(int i=0;i<10;i++)   sum=(sum+DP[N][i])%MOD;
    cout << sum%MOD;
    return 0;
}