BAEKJOON 2688 - Non-Decreasing Digits

문제: https://www.acmicpc.net/problem/2688

문제

A number is said to be made up of non-decreasing digits if all the digits to the left of any digit is less than or equal to that digit. For example, the four-digit number 1234 is composed of digits that are non-decreasing. Some other four-digit numbers that are composed of non-decreasing digits are 0011, 1111, 1112, 1122, 2223. As it turns out, there are exactly 715 four-digit numbers composed of non-decreasing digits.

Notice that leading zeroes are required: 0000, 0001, 0002 are all valid four-digit numbers with nondecreasing digits.

For this problem, you will write a program that determines how many such numbers there are with a specified number of digits

입력

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by a decimal integer giving the number of digits N, (1 ≤ N ≤ 64).

출력

For each data set there is one line of output. It contains the data set number followed by a single space, followed by the number of N digit values that are composed entirely of non-decreasing digits

예제 입력 

3
2
3
4

예제 출력 

55
220
715

힌트

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2010 Greater New York Programming Contest E번

• 문제를 번역한 사람: baekjoon

링크

• ACM-ICPC Live Archive
• Sphere Online Judge

알고리즘 분류

• 다이나믹 프로그래밍

우선 가장 뒷자리 수를 0~9 사이의 값으로 정하고 주어진 자릿수를 채울 수 있는 경우의 수를 찾아 값을 구할 수 있는 재귀 함수를 만들어야 됩니다.

이후 n이 클 경우를 대비하여 memoization 을 사용하면 시간 복잡도를 줄일 수 있습니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
ll cache[10][65];
ll getCount(int n, int digit)
{
    if (digit == 1)
    {
        return 1;
    }
 
    ll& ret = cache[n][digit];
    if (ret != -1)
        return ret;
    ll sum = 0;
    for (int i = 0; i <= n; i++)
    {
        sum += getCount(i, digit - 1);
    }
    ret = sum;
    return ret;
}
 
int main() 
{
    memset(cache, -1, sizeof(cache));
    int cases, n;
    cin >> cases;
    for (int c = 0; c < cases; c++)
    {
        cin >> n;
        ll ret = 0;
        for (int i = 0; i < 10; i++)
        {
            ret += getCount(i, n);
        }
        cout << ret << endl;
    }
 
    return 0;
}