문제 개요
이 문제에서는 숫자 N이 주어지며, 왼쪽(최상위 자릿수)에서 오른쪽(최하위 자릿수)으로 갈수록 자릿값이 엄격하게 증가하는 모든 n자리 숫자를 출력해야 합니다. 즉, 각 자릿수는 바로 오른쪽에 있는 자릿수보다 반드시 작아야 합니다.
예시를 통해 문제를 살펴보겠습니다.
입력 − n = 2
출력 −
01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
설명 − 출력된 모든 숫자에서 왼쪽 자릿수는 항상 오른쪽 자릿수보다 작습니다. 예를 들어 12에서는 1 < 2, 89에서는 8 < 9가 성립합니다.
해결 접근 방식
이 문제는 재귀(Recursion)를 활용하면 효율적으로 해결할 수 있습니다. 최상위 자릿수(MSB)부터 시작해 한 자릿수씩 채워 나가며, 현재 위치의 자릿수가 i라면 다음 위치에는 반드시 i+1부터 9 사이의 숫자만 올 수 있습니다. 이렇게 하면 별도의 검증 과정 없이도 자동으로 엄격하게 증가하는 조건이 만족됩니다.
알고리즘 동작 원리
- 시작 자릿수(start), 누적된 숫자 문자열(out), 남은 자릿수(n)를 매개변수로 받는 재귀 함수를 정의합니다.
- 남은 자릿수 n이 0이 되면 완성된 숫자를 출력하고 함수를 종료합니다.
- start부터 9까지의 각 숫자 i에 대해 현재 문자열에 i를 추가한 뒤, 시작 값을 i+1로, 남은 자릿수를 n-1로 줄여 재귀 호출합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
void printIncreasingNumbers(int start, string out, int n) {
if (n == 0){
cout<<out<<" ";
return;
}
for (int i = start; i <= 9; i++){
string str = out + to_string(i);
printIncreasingNumbers(i + 1, str, n - 1);
}
}
int main() {
int n = 3;
cout<<"All "<<n<<" digit strictly increasing numbers are :\n";
printIncreasingNumbers(0, "", n);
return 0;
}실행 결과
All 3 digit strictly increasing numbers are − 012 013 014 015 016 017 018 019 023 024 025 026 027 028 029 034 035 036 037 038 039 045 046 047 048 049 056 057 058 059 067 068 069 078 079 089 123 124 125 126 127 128 129 134 135 136 137 138 139 145 146 147 148 149 156 157 158 159 167 168 169 178 179 189 234 235 236 237 238 239 245 246 247 248 249 256 257 258 259 267 268 269 278 279 289 345 346 347 348 349 356 357 358 359 367 368 369 378 379 389 456 457 458 459 467 468 469 478 479 489 567 568 569 578 579 589 678 679 689 789
정리
이 알고리즘은 백트래킹과 유사한 구조로 동작하며, 시간 복잡도는 가능한 숫자 조합의 개수에 비례합니다. n자리 엄격 증가 숫자의 개수는 10개의 자릿수(0~9) 중 n개를 선택하는 조합과 같으므로 C(10, n)개입니다. 재귀 호출마다 다음 자릿수의 범위를 제한함으로써 불필요한 탐색을 줄일 수 있어 매우 효율적인 방식입니다.