백준 10844번 쉬운 계단수

문제 링크입니다:https://www.acmicpc.net/problem/10844

예전이라면 손도 못 댔을 문제인데 동적계획법을 익히고 나니 풀리는게 신기할 따름입니다.

/*

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

길이가 N인 계단 수가 몇개인지를 구하시오

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MOD = 1000000000;

int cache[10][101]; //cache[digit][length], digit으로 시작하는 숫자, length는 길이

 

int stairNum(int digit, int length)

{

        if (digit < 0 || digit>9) //한자리수만 가능

               return 0;

        int &result = cache[digit][length];

        if (result != -1)

               return result;

        //다음 수를 하나 작은 수 혹은 하나 큰 수로

        return result = (stairNum(digit - 1, length - 1) + stairNum(digit + 1, length - 1)) % MOD;

}

 

int main(void)

{

        int N;

        cin >> N;

        if (N < 1 || N>100)

               exit(-1);

 

        memset(cache, -1, sizeof(cache));

        for (int i = 0; i < 10; i++)

               cache[i][1] = 1; //초기값(1~9까지는 1씩)

        int sum = 0;

        for (int i = 1; i <= 9; i++)

        {

               sum += stairNum(i, N);//0으로 시작하는 숫자는 없으므로 1부터

               sum %= MOD; //이 코드를 작성하지 않으면 틀렸다고 나옵니다.

        }

        cout << sum << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~