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

이 문제에서는 두 개의 정수 값이 주어집니다. N은 숫자의 자릿수 개수를 나타내고 sum은 숫자의 자릿수 합을 나타냅니다. 우리의 임무는 주어진 자릿수와 자릿수의 합으로 가장 큰 수를 찾는 것입니다. .

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

Input : N = 3, sum = 15
Output : 960

솔루션 접근 방식

문제를 해결하는 간단한 접근 방식은 모든 N 자리 숫자를 가장 큰 것에서 가장 작은 것까지 순회하는 것입니다. 숫자 합을 찾고 합과 같으면 숫자를 반환합니다.

예시

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

#include <iostream>
using namespace std;
int digitSum(int n){
   int sum = 0; 
   while(n){
      sum += n%10; 
      n = n/10;
   }
   return sum;
}
int findLargestNumWithSum(int N, int sum){
   if (sum == 0){
      if(N == 1)
         return -1;
      else
         return -1;
   }
   if (sum > 9*N){
      return -1;
   }
   int num = 1;
   for(int i = 0; i < N; i++) 
      num *= 10;
   while(1){
      if(digitSum(num) == sum){
         return num;
      }
      num -- ;
      if(num == 0)
         return -1;
   }
}
int main(){
   int sum = 25, N = 3;
   cout<<"The largest "<<N<<" digit number with sum "<<sum<<" is "<< findLargestNumWithSum(N, sum);
   return 0;
}

출력

The largest 3 digit number with sum 25 is 997

문제를 해결하는 또 다른 방법은 Greedy Approach를 사용하는 것입니다. MSB에서 시작하여 합계에서 가능한 가장 높은 숫자를 배치하고 합계에서 빼는 방식으로 이를 수행합니다.

이 단계를 N 번 수행하면 필요한 수를 얻을 수 있습니다. 따라서 합이 9보다 크면 현재 자릿수에 9를 배치하고 9보다 작으면 합을 현재 자릿수에 배치합니다. MSB에서 LSB 배치 숫자까지 모든 숫자에 대해 이 프로세스를 수행하십시오.

예시

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

#include <iostream>
using namespace std;
int findLargestNumWithSum(int N, int sum){
   if (sum == 0){
      if(N == 1)
         return -1;
      else
         return -1;
   }
   if (sum > 9*N){
      return -1;
   }
   int num = 0;
   for (int i = 0; i < N; i++){
      if (sum >= 9){
         num += 9;
         sum -= 9;
         if(i < (N - 1)){
            num *= 10;
         }
      }
      else{
         num += sum;
         sum = 0;
         if( i < (N - 1)) 
             num *= 10;
      }
   }
   return num;
}
int main(){
   int sum = 25,
   N = 3;
   cout<<"The largest "<<N<<" digit number with sum "<<sum<<" is "<<findLargestNumWithSum(N, sum);
   return 0;
}

출력

The largest 3 digit number with sum 25 is 997