n자리의 감소하지 않는 숫자의 총 개수

숫자는 모든 자릿수(첫 번째 자리 제외)가 이전 자릿수보다 작지 않은 경우 감소하지 않는다고 합니다. 이 알고리즘의 경우 N자리 숫자에 감소하지 않는 숫자가 몇 개 있는지 찾아야 합니다.

count(n, d) 함수에 길이가 n이고 문자 d로 끝나는 감소하지 않는 숫자가 몇 개 있는지 계산하면 다음과 같은 관계를 작성할 수 있습니다.

$$count(n,d)=\displaystyle\sum\limits_{i=0}^d count(n-1,i)\\total=\displaystyle\sum\limits_{d=0}^{n-1 } 개수(n-1,d)$$

입력 및 출력

Input:
Number of digits, say 3.
Output:
The possible non decreasing numbers. Here it is 220.
Non decreasing numbers are like 111, 112, 123, 789, 569 etc.

알고리즘

countNumbers(n)

입력: 주어진 값입니다.

출력: n자리 숫자에서 감소하지 않는 값의 수입니다.

Begin
   define count matrix of order (10 x n+1), and fill with 0
   for i := 0 to 9, do
      count[i, 1] := 1
   done

   for digit := 0 to 9, do
      for len := 2 to n, do
         for x := 0 to digit, do
            count[digit, len] := count[digit, len] + count[x, len-1]
         done
      done
   done

   nonDecNum := 0
   for i := 0 to 9, do
      nonDecNum := nonDecNum + count[i, n]
   done

   return nonDecNum
End

예

#include<iostream>
using namespace std;

long long int countNumbers(int n) {
   long long int count[10][n+1];    //to store total non decreasing number starting with i digit and length j

   for(int i = 0; i<10; i++)
      for(int j = 0; j<n+1; j++)
         count[i][j] = 0;     //initially set all elements to 0

   for (int i = 0; i < 10; i++)    //set non decreasing numbers of 1 digit
      count[i][1] = 1;

   for (int digit = 0; digit <= 9; digit++) {     //for all digits 0-9
      for (int len = 2; len <= n; len++) {       //for those numbers (length 2 to n)
         for (int x = 0; x <= digit; x++)
            count[digit][len] += count[x][len-1];     //last digit x <= digit, add with number of len-1
      }
   }

   long long int nonDecNum = 0;

   for (int i = 0; i < 10; i++)    //total non decreasing numbers starting with 0-9
      nonDecNum += count[i][n];
   return nonDecNum;
}

int main() {
   int n = 3;
   cout << "Enter number of digits: "; cin >> n;
   cout << "Total non decreasing numbers: " << countNumbers(n);
}

출력

Enter number of digits: 3
Total non decreasing numbers: 220