[DP] 10844번 쉬운 계단 수

10844번 쉬운 계단 수

 

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

 

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

 

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

예제 입력

1

2

 

예제 출력

9

17

 

해결방법

이친수문제와 비슷한 유형의 DP 문제이다

 

d[n][0] : 0으로 끝나는 계단 수

d[n][1] : 1로 끝나는 계단 수

:

d[n][9] : 9로 끝나는 계단 수

 

n자리 계단수를 구하고자하면 0~9로 끝나는 n자리 계단수의 합을 구해야한다

일단, 초기값을 설정해줘야 한다

d[1][0] = 0;
for(int i=1; i<=9; i++){
    d[1][i] = 1;
}

 

이제 2부터는 반복문을 통하여 bottom-up 방식으로 구현한다

이 때, 0과 9로 끝나는 경우는 계단이 하나밖에 존재하지 않으므로 예외 처리를 시켜준다

void dp(){
    // 초기화
    for(int i=1; i<=9; i++){
        d[1][i] = 1;
    }
    
    for(int i=2; i<=n; i++){
        // 0,9 의 경우
        d[i][0] = d[i-1][1] % 1000000000;
        d[i][9] = d[i-1][8]  % 1000000000;
        
        // 1~8 의 경우
        for(int j=1; j<=8; j++){
            d[i][j] = (d[i-1][j-1] + d[i-1][j+1]) % 1000000000;
        }
    }
}

 

소스코드

#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
#define MAX 101
using namespace std;

int n;
long long ans;
long long d[MAX][10];

/*
 
 순환식 :
 d[n][0] : d[n-1][1]
 d[n][i] : d[n-1][i-1] + d[n-1][i+1]
 d[n][9] : d[n-1][8]
 
 */

void dp(){
    // 초기화
    for(int i=1; i<=9; i++){
        d[1][i] = 1;
    }
    
    for(int i=2; i<=n; i++){
        // 0,9 의 경우
        d[i][0] = d[i-1][1] % 1000000000;
        d[i][9] = d[i-1][8]  % 1000000000;
        
        // 1~8 의 경우
        for(int j=1; j<=8; j++){
            d[i][j] = (d[i-1][j-1] + d[i-1][j+1]) % 1000000000;
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    dp();
    
    ans = 0;
    for(int i=0; i<=9; i++){
        ans += d[n][i];
    }
    cout << ans % 1000000000 << "\n";
    
    return 0;
}