문제 개요
이 문제에서는 두 값이 주어집니다. 하나는 자릿수의 합(sum), 다른 하나는 자릿수(digit)입니다. 우리의 목표는 주어진 자릿수와 자릿수의 합 조건을 모두 만족하는 가장 작은 수를 찾는 것입니다.
예제를 통해 문제를 이해해 보겠습니다.
입력
sum = 15, digit = 2
출력
69
설명
자릿수의 합이 15인 두 자리 수는 69, 78, 87, 96으로 총 네 가지가 있습니다. 이 중 가장 작은 수는 69입니다.
풀이 접근 방법
가장 단순한 방법은 해당 자릿수를 가진 모든 수를 하나씩 검토하면서 자릿수의 합이 주어진 값과 일치하는 가장 작은 수를 찾는 것입니다. 하지만 이 방법은 경우의 수가 기하급수적으로 늘어나므로 매우 비효율적입니다.
훨씬 효율적인 방법은 그리디(Greedy) 알고리즘을 활용하는 것입니다. 숫자를 구성할 때 마지막 자릿수, 즉 최하위 자릿수(LSB)부터 채워 나갑니다. 각 자리에 배치할 수 있는 가장 큰 값을 우선적으로 넣고, 남은 합을 앞자리로 넘겨줍니다.
여기서 핵심 아이디어는 최하위 자릿수(LSB)를 최대한 크게, 최상위 자릿수(MSB)를 최대한 작게 유지하는 것입니다. 숫자의 크기는 높은 자릿수의 값에 큰 영향을 받기 때문에, 낮은 자릿수에 큰 숫자(9)를 몰아주면 전체 수가 가장 작아집니다.
또한 최상위 자릿수가 0이 되면 안 되므로, 처음부터 합에서 1을 미리 빼두어 MSB에 최소 1이 배정되도록 처리합니다.
구현 코드
#include <iostream>
using namespace std;
void findSmallestNumWithSum(int digit, int sum) {
// 합이 0인 경우 처리
if (sum == 0) {
if(digit == 1)
cout<<"Smallest number is 0";
else
cout<<"Smallest number with sum cannot be found";
return ;
}
// 만들 수 없는 경우: 각 자릿수의 최대 합은 9*digit
if (sum > 9*digit) {
cout<<"Smallest number with sum cannot be found";
return ;
}
int number[digit];
sum -= 1; // MSB에 최소 1을 확보하기 위해 미리 차감
// 뒤쪽 자릿수부터 가능한 한 큰 값(9)을 채움
for (int i = digit-1; i>0; i--) {
if (sum > 9) {
number[i] = 9;
sum -= 9;
} else {
number[i] = sum;
sum = 0;
}
}
// 남은 합 + 1을 MSB에 배정
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
코드 동작 원리
코드의 동작 흐름을 단계별로 살펴보겠습니다.
1. 예외 처리: 합이 0이면서 자릿수가 1이면 답은 0입니다. 반면 자릿수가 2 이상이면 선행 0이 허용되지 않으므로 조건을 만족하는 수가 없습니다. 또한 합이 9 × 자릿수보다 크면 어떤 수도 조건을 만족할 수 없습니다.
2. 뒤에서부터 채우기: 합에서 1을 미리 빼서 최상위 자릿수에 사용할 값을 확보한 뒤, 마지막 자릿수부터 시작해 남은 합이 9보다 크면 9를 배치하고, 그렇지 않으면 남은 합 전체를 배치합니다.
3. 최상위 자릿수 결정: 루프가 끝난 후 남은 합에 확보해 둔 1을 더해 MSB에 배정합니다.
예를 들어 sum = 15, digit = 3인 경우, 뒤의 두 자리에 5와 9를 배치하고 첫 자리에 1을 두어 159라는 가장 작은 수를 얻습니다.
시간 복잡도
각 자릿수를 한 번씩만 채우므로 시간 복잡도는 O(digit)이며, 결과를 저장하는 배열 때문에 공간 복잡도 역시 O(digit)입니다. 완전 탐색 방식과 비교했을 때 압도적으로 효율적입니다.