백준 2688번 줄어들지 않아

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

http://jaimemin.tistory.com/359와 매우 유사한 문제였습니다.

계단수와는 다르게 이 문제에서 구하는 것은 줄어들지 않는 숫자이므로 계단수보다는 훨씬 많은 경우의 수가 존재합니다.

따라서, int형 대신 long long형으로 결과를 구해야합니다.

계단수 문제와 같이 1~9는 이미 조건이 성립하는 숫자이므로 캐쉬에 미리 저장시켜놓고 자릿수 길이를 줄여가면서 경우의 수를 구하면되는 DP 문제였습니다.

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 64 + 1;

 

int T, n;

long long cache[10][MAX]; //시작하는 수, 자리수 길이

 

long long nondecreasingNum(int start, int length)

{

        long long &result = cache[start][length];

        if (result != -1)

                 return result;

 

        //start~9까지 모두 가능

        result = nondecreasingNum(start, length - 1);

        for (int num = start + 1; num <= 9; num++)

                 result += nondecreasingNum(num, length - 1);

        return result;

}

 

int main(void)

{

        cin >> T;

 

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

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

                 cache[i][1] = 1; //초기값(0~9는 모두 성립)

 

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

        {

                 cin >> n;

 

                 long long result = 0;

                 //0~9로 시작하는 숫자 경우의 수 모두 더한다

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

                         result += nondecreasingNum(i, n);

                 cout << result << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

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