[BOJ=10844]쉬운계단수

DP문제

문제의 조건

45654 이런 수는 계단수라고 함 

: 인접한 수들의 차이가 +1, -1 가 나는 수를 '''계단수'''

이때 수의 자리수의 길이가 입력될 때 값을 구하는 것.

가장 맨앞의 수는 0 이 될 수 없고, 즉, 1-9 까지 가장 맨앞자리 차지함.

그 이후 0-9 까지 의 수가 적힌 수들이 있음.

F(N) 이라고 공식을 세운다면,

처음 F(1) = 9 이고 이는 [1,2,3,4,5,6,7,8,9]

 까지 총 9개의 수가 있음.

F(2) = 17 이고, [10,12, 21, 23, 32, 34, ..., 87, 89, 98] 총 17개의 수가 있음.

이것을 생각해보면, 

가장 앞자리 수는 0을 제외한 수.

이후 그 뒷 수는 0을 포함하는 수로 구성이 될 수 있음.

각 자리수 마다, memo의 위치를 정함.

수가 0일때, 1일때, .... 9일때 

이전 수에서 인접한 갯수가 이때 더해져야함.

 

인 경우가 됨.

그런데 특수한 경우가 양쪽 끝에 있으므로 첫자리 수가 0 이거나 혹은 9이거나 하는 경우는

case 0)

 

case 9)

 

로 이루어 져야 함. 왜냐면 9와 차이가 1나는 수는 8 뿐이고

0과 차이나는 수는 1 뿐이므로. 

그리고 입력으로 주어진 자리수의 memo 배열의 값을 인덱스 0 을 제외한 값을 모두 더하면 해당 자리수에서의 갯수가 됨.

 

 

그래서 그리면 위와 같아짐.

#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;
typedef vector<LL> VLL;
VLL memo[111];
const LL DIV = 1e+9;
int main() {
    for (int i = 0; i < 111; i++) {
        memo[i] = VLL(10, -1);
    }
 
    for (int i = 0; i < 10; i++) {
        memo[1][i] = 1;
    }
 
    for (int i = 1; i < 111; i++) {
        for (int j = 0; j < 10; j++) {
            if (memo[i][j] == -1) {
                if (j == 0) {
                    memo[i][j] = memo[i - 1][j + 1]% DIV;
                }
                else if (j == 9) {
                    memo[i][j] = memo[i - 1][j - 1]% DIV;
                }
                else { // j ~ [1,8]
                    memo[i][j] = (memo[i - 1][j - 1] + memo[i - 1][j + 1])% DIV;
                }
            }
        }
    }
 
    int want = 0;
    scanf("%d", &want);
    
    LL ans = 0;
    for (int i = 1; i < 10; i++) {
        ans = (ans + memo[want][i]) % DIV;
    }
    printf("%lld", ans);
 
    return 0;
}