자릿수의 합이 값과 같은 숫자 찾기

숫자 n과 값이 있습니다. 우리는 모든 n자리 숫자를 찾아야 합니다. 여기서 모든 n자리 s의 합은 주어진 값과 같습니다. 여기서 0은 숫자로 계산되지 않습니다.

숫자 n은 1에서 100 사이여야 하고 값은 1에서 500 사이여야 합니다.

입력 및 출력

Input:
This algorithm takes number of digits, and the sum value.
Let the digit count is 3. and sum is 15.
Output:
Display the number of different 3-digit numbers whose sum is 15.
The result is 69. (There are 69 different 3-digit numbers whose sum is 15)

알고리즘

개수(숫자, 합계)

입력: 주어진 값의 숫자입니다.

출력: 숫자를 세어 보세요.

Begin
   if digit = 0, then
      return true when sum = 0

   if memTable[digit, sum] is not vacant, then
      return memTable[digit, sum]
   answer := 0

   for i := 0 to 9 do
      if sum – i >= 0, then
         answer := answer + count(digit – 1, sum - i)
   done

   return memTable[digit, sum] := answer
End

numberCount(숫자, 합계)

입력: 숫자의 자릿수, 주어진 값입니다.

출력: 해당 유형의 숫자는 몇 개입니까?

Begin
   define memTable and make all space vacant
   res := 0

   for i := 1 to 9, do
      if sum – i >= 0, then
         res := res + count(digit – 1, sum - i)
   done

   return result
End

예시

#include<iostream>
#define ROW 101
#define COL 501
using namespace std;

unsigned long long int memTable[ROW][COL];

unsigned long long int count(int digit, int sum) {
   if (digit == 0)    //for 0 digit number check if the sum is 0 or not
      return sum == 0;

   if (memTable[digit][sum] != -1)    //when subproblem has found the result, return it
      return memTable[digit][sum];

   unsigned long long int ans = 0;    //set the answer to 0 for first time

   for (int i=0; i<10; i++)    //count for each digit and find numbers starting with it
      if (sum-i >= 0)
         ans += count(digit-1, sum-i);
   return memTable[digit][sum] = ans;
}

unsigned long long int numberCount(int digit, int sum) {
   for(int i = 0; i<ROW; i++)    //initially all entries of memorization table is -1
      for(int j = 0; j<ROW; j++)
         memTable[i][j] = -1;
               
   unsigned long long int result = 0;
   for (int i = 1; i <= 9; i++)    //count for each digit and find numbers starting with it
      if (sum-i >= 0)
         result += count(digit-1, sum-i);
   return result;
}

int main() {
   int digit, sum;
   cout << "Enter digit count: "; cin >> digit;
   cout << "Enter Sum: "; cin >> sum;
   cout << "Number of values: " << numberCount(digit, sum);
}

출력

Enter digit count: 3
Enter Sum: 15
Number of values: 69