이 문제에서는 두 개의 숫자 n과 sum이 주어집니다. 우리가 해야 할 일은 각 자릿수의 합이 sum과 정확히 일치하는 모든 n자리 숫자를 찾아 출력하는 것입니다. 단, 앞자리가 0으로 시작하는 숫자(선행 0)는 유효한 n자리 숫자로 간주하지 않습니다.
문제 이해하기
예시를 통해 문제를 살펴보겠습니다.
입력: n = 2 , sum = 5
출력: 14 23 32 41 50
설명: 위 모든 숫자의 자릿수 합은 5입니다.
해결 접근 방법
이 문제를 해결하려면 자릿수의 합이 주어진 sum 값과 일치하는 모든 n자리 숫자를 찾아야 합니다. 이를 위해 재귀(Recursion) 기법을 사용합니다.
핵심 아이디어는 다음과 같습니다.
- 각 자릿수 위치에 0부터 9까지의 값을 하나씩 고정합니다.
- 단, 가장 앞자리(최상위 자릿수)는 1부터 9 사이의 값만 허용하여 선행 0을 방지합니다.
- 한 자릿수를 채울 때마다 남은 합에서 해당 숫자만큼 차감하고, 다음 자릿수를 채우기 위해 재귀 호출을 진행합니다.
- 모든 자릿수를 채웠을 때(index == n) 남은 합이 0이라면, 조건을 만족하는 숫자이므로 출력합니다.
구현 예제
위 접근 방식을 구현한 C++ 프로그램입니다.
#include <iostream>
using namespace std;
void PrintNumberWithDigitSum(int n, int sum, char* out, int index) {
if (index > n || sum < 0)
return;
if (index == n) {
if(sum == 0) {
out[index] = ' ';
cout << out << " ";
}
return;
}
for (int i = 0; i <= 9; i++) {
out[index] = i + '0';
PrintNumberWithDigitSum(n, sum - i, out, index + 1);
}
}
void numberWithSum(int n, int sum) {
char out[n + 1];
for (int i = 1; i <= 9; i++) {
out[0] = i + '0';
PrintNumberWithDigitSum(n, sum - i, out, 1);
}
}
int main() {
int n = 3, sum = 6;
cout<<"All "<<n<<" digit numbers with sum "<<sum<<" are :\n";
numberWithSum(n, sum);
return 0;
}
실행 결과
All 3 digit numbers with sum 6 are −
105 114 123 132 141 150 204 213 222 231 240 303 312 321 330 402 411 420 501 510 600
코드 설명
- PrintNumberWithDigitSum 함수: 현재 index 위치에 0~9의 숫자를 하나씩 넣어보며 재귀적으로 탐색합니다. 남은 합(sum)이 음수가 되거나 인덱스가 범위를 초과하면 가지치기(pruning)를 통해 불필요한 탐색을 줄입니다.
- numberWithSum 함수: 첫 번째 자릿수에 1~9의 값을 설정하여 선행 0이 포함되지 않도록 하고, 나머지 자릿수는 재귀 함수에 맡깁니다.
- 종료 조건: index가 n에 도달했을 때 남은 합이 0이면 해당 숫자를 결과로 출력합니다.
이 알고리즘은 백트래킹 방식으로 동작하며, 시간 복잡도는 최악의 경우 O(10^n)이지만 가지치기를 통해 실제 탐색 범위를 크게 줄일 수 있습니다.