Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 자릿수 개수와 자릿수 합이 주어졌을 때 만들 수 있는 가장 큰 수 찾기

이 문제에서는 두 개의 정수가 주어집니다. 하나는 숫자의 자릿수 개수를 나타내는 N, 다른 하나는 각 자릿수의 합을 나타내는 sum입니다. 우리의 과제는 주어진 자릿수 개수와 자릿수 합 조건을 모두 만족하는 가장 큰 수를 찾는 것입니다.

문제 이해하기

예시를 통해 문제를 살펴보겠습니다.

입력 : N = 3, sum = 15
출력 : 960

3자리 숫자 중 각 자릿수의 합이 15가 되는 가장 큰 수는 960입니다(9 + 6 + 0 = 15). 앞자리부터 최대한 큰 숫자를 배치하는 것이 핵심 아이디어입니다.

방법 1: 완전 탐색(Brute Force)

가장 직관적인 해결 방법은 N자리 숫자를 가장 큰 값부터 작은 값까지 차례로 검사하면서, 각 숫자의 자릿수 합을 계산해 주어진 sum과 일치하는지 확인하는 것입니다. 조건을 만족하는 첫 번째 숫자가 곧 정답이 됩니다.

예제 코드

#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){
    // 자릿수 합이 0이거나 가능한 최댓값(9*N)을 초과하면 답이 없음
    if (sum == 0 || sum > 9 * N)
        return -1;

    // N자리 최댓값부터 내려가며 탐색
    int num = 1;
    for(int i = 0; i < N; i++)
        num *= 10;

    while(num > 0){
        if(digitSum(num) == sum)
            return num;
        num--;
    }
    return -1;
}

int main(){
    int sum = 25, N = 3;
    cout<<"자릿수 합이 "<<sum<<"인 "<<N<<"자리 숫자 중 가장 큰 수는 "<<findLargestNumWithSum(N, sum);
    return 0;
}

실행 결과

자릿수 합이 25인 3자리 숫자 중 가장 큰 수는 997

이 방법은 구현이 간단하지만, 최악의 경우 거의 모든 N자리 숫자를 검사해야 하므로 O(10N)에 가까운 시간이 걸립니다. N이 조금만 커져도 실용성이 크게 떨어집니다.

방법 2: 그리디(Greedy) 접근법

훨씬 효율적인 방법은 그리디 알고리즘을 활용하는 것입니다. 최상위 자릿수(MSB)부터 시작해, 현재 남은 sum으로 해당 자릿수에 넣을 수 있는 가장 큰 숫자를 배치하고 그만큼 sum에서 차감하는 방식입니다.

구체적인 규칙은 다음과 같습니다.

  • 남은 sum이 9보다 크거나 같으면 → 현재 자릿수에 9를 배치하고 sum에서 9를 뺍니다.
  • 남은 sum이 9보다 작으면 → 현재 자릿수에 sum 값 그대로를 배치하고 sum을 0으로 만듭니다.

이 과정을 MSB부터 LSB까지 총 N번 반복하면 원하는 숫자를 얻을 수 있습니다.

예제 코드

#include <iostream>
using namespace std;

int findLargestNumWithSum(int N, int sum){
    // 자릿수 합이 0이거나 가능한 최댓값(9*N)을 초과하면 답이 없음
    if (sum == 0 || 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<<"자릿수 합이 "<<sum<<"인 "<<N<<"자리 숫자 중 가장 큰 수는 "<<findLargestNumWithSum(N, sum);
    return 0;
}

실행 결과

자릿수 합이 25인 3자리 숫자 중 가장 큰 수는 997

두 방법의 시간 복잡도 비교

완전 탐색: 후보 숫자를 하나씩 검사해야 하므로 지수 시간(O(10N))이 소요됩니다.

그리디 접근법: 각 자릿수를 한 번씩만 결정하면 되므로 O(N)의 시간 복잡도를 가집니다. 실제 문제 해결에는 그리디 방식이 권장됩니다.

마무리

주어진 자릿수 개수와 자릿수 합으로 만들 수 있는 가장 큰 수를 찾는 문제는 "앞자리부터 최대한 큰 숫자(9)를 채우고 남은 합을 뒷자리로 넘긴다"는 그리디 전략으로 선형 시간 안에 해결할 수 있습니다. 다만 sum이 0이거나 9×N을 초과하는 경우처럼 유효한 답이 존재하지 않는 경계 조건을 반드시 먼저 처리해야 한다는 점을 기억하세요.