C++에서 주어진 자릿수와 자릿수의 합으로 가장 작은 수 찾기

이 문제에서 우리는 sum(자릿수의 합을 나타냄)과 digit(자릿수를 나타냄)의 두 값을 받습니다. 우리의 임무는 주어진 자릿수와 자릿수의 합으로 가장 작은 수를 찾는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

sum = 15, dgiti = 2

출력

69

설명

합이 15인 2자리 숫자는 모두 69, 78, 87, 96입니다.

솔루션 접근 방식

이 문제에 대한 간단한 해결책은 digitcount가 있는 모든 숫자를 숫자로 간주하고 숫자의 합이 합과 같은 가장 작은 숫자를 찾는 것입니다.

효율적인 솔루션은 욕심 많은 접근 방식을 사용하는 것입니다. 마지막 숫자의 요소, 즉 숫자의 LSB를 채워 숫자를 생성합니다. LSB에 대해 가능한 가장 큰 요소를 고려하고 다음 위치로 이동합니다.

LSB는 최대한 크게, MSB는 최대한 작게 유지하도록 노력하겠습니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include <iostream>
using namespace std;
void findSmallestNumWithSum(int digit, int sum) {
   if (sum == 0) {
      if(digit == 1)
         cout<<"Smallest number is 0";
      else
         cout<<"Smallest number with sum cannot be found";
      return ;
   }
   if (sum > 9*digit) {
      cout<<"Smallest number with sum cannot be found";
      return ;
   }
   int number[digit];
   sum -= 1;
   for (int i = digit-1; i>0; i--) {
      if (sum > 9) {
         number[i] = 9;
         sum -= 9;
      } else {
         number[i] = sum;
         sum = 0;
      }
   }
   number[0] = sum + 1;
   cout<<"Smallest number is ";
   for (int i=0; i<digit; i++)
      cout<<number[i];
}
int main() {
   int sum = 15, digit = 3;
   findSmallestNumWithSum(digit, sum);
   return 0;
}

출력

Smallest number is 159