[C++] 백준 10844 [쉬운 계산 수]

문제설명

1232, 1201, 1012 과 같이 옆 자리수와 연속된 수를 계단수라고 정의한다.
길이가 N인 계단수의 갯수를 구해보자.
단, 맨 앞자리가 0인 경우는 제외한다.

풀이방법

Top-down 풀이방식이다.
Cache array는 이중 배열로 구현하였다.
DP(a, b)의 정의 : b번째 자리수의 숫자가 a이고, 총 자릿수가 b인 계단수의 갯수
문제의 정답은 DP(0, N) + DP(1, N) + DP(2, N) … DP(9, N)이 된다.
기저조건은 첫번째 자리수인 경우 1을 리턴하되, a가 0인 경우에는 문재의 조건에 따라 0을 리턴한다.
a가 만약 0인 경우, DP(1, b-1)과 같다. 왜냐하면 연속된 수가 1 밖에 없기 때문이다.
a가 만약 9인 경우, DP(8, b-1)과 같다. 왜냐하면 연속된 수가 8 밖에 없기 때문이다.
그 외의 경우 DP(a-1, b-1) + DP(a+1, b-1)과 같다. 연속된 숫자는 항상 2개가 존재한다.

점화식

\(DP(0, b) = DP(1, b-1)\)
\(DP(9, b) = DP(8, b-1)\)
\(DP(a, b) = DP(a-1, b-1) + DP(a+1, b-1)\) (단, a는 1이상 8이하의 자연수)

위 점화식에 따라 코드를 작성하면 아래와 같다.

소스코드

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

int cache[10][101];

int DP(int a, int b){
    if(b == 1 && a == 0) return 0;
    if(b == 1) return 1;

    int& ret = cache[a][b];
    if(ret != - 1)  return ret;

    if(a == 0) return ret = DP(1, b-1);
    if(a == 9) return ret = DP(8, b-1);
    return ret = (DP(a-1, b-1) + DP(a+1, b-1)) % 1000000000;
}

int main(){
    int N, result = 0;
    cin >> N;
    memset(cache, -1, sizeof(cache));
    for(int i=0; i<10; i++) result = (result + DP(i, N)) % 1000000000;
    cout << result;
}