정수형 변수 N에 양의 정수 값이 저장되어 있다고 가정해 보겠습니다. 이 문제의 목표는 재귀(Recursion) 기법을 활용하여 주어진 값 N보다 작으면서 숫자 1, 3 또는 두 숫자의 조합으로만 구성된 모든 수를 찾아 출력하는 것입니다.
입출력 시나리오 살펴보기
입력 - int num = 40
출력 - 숫자 1 또는 3으로만 구성된 N 미만의 모든 수: 33 31 13 11 3 1
설명 - 변수 num에 양의 정수 값 40이 저장되어 있습니다. 재귀적으로 숫자 1, 3 또는 둘 다를 포함하는 수를 찾으면, 40보다 작은 수는 1, 3, 11, 13, 31, 33입니다.
입력 - int num = 5
출력 - 숫자 1 또는 3으로만 구성된 N 미만의 모든 수: 3 1
설명 - 변수 num에 양의 정수 값 5가 저장되어 있습니다. 재귀적으로 조건을 만족하는 수를 찾으면, 5보다 작은 수는 1과 3뿐입니다.
입력 - int num = 1
출력 - 잘못된 입력(Wrong Input)
설명 - 변수 num에 양의 정수 값 1이 저장되어 있습니다. 1보다 작은 양의 정수는 존재하지 않으므로 프로그램은 "잘못된 입력" 메시지를 출력합니다.
프로그램에 적용된 접근 방식
정수형 변수 num을 입력받고, 이 값을 매개변수로 전달하며 Recursive_Numbers(num) 함수를 호출합니다.
Recursive_Numbers(num) 함수 내부 동작은 다음과 같습니다.
bool 타입의 변수 check를 선언하고 1(true)로 초기화합니다.
num이 0보다 큰 경우, temp가 0보다 크고 check가 1인 동안 WHILE 반복문을 수행합니다. 각 자릿값 digit은 temp % 10으로 구합니다.
digit이 1도 아니고 3도 아니라면 check를 0(false)으로 설정합니다. 이후 temp = temp / 10으로 갱신하여 다음 자릿수를 검사합니다.
반복문 종료 후 check가 여전히 1이라면 해당 num은 조건을 만족하므로 출력합니다.
마지막으로 Recursive_Numbers(num - 1) 형태로 함수를 재귀 호출하여 더 작은 수를 검사합니다.
예제 코드
#include <iostream>
using namespace std;
void Recursive_Numbers(int num){
bool check = 1;
int temp = num;
if(num > 0){
while(temp > 0 && check == 1){
int digit = temp % 10;
if (digit != 1 && digit != 3){
check = 0;
}
temp = temp / 10;
}
if(check == 1){
cout<< num << " ";
}
Recursive_Numbers(num - 1);
}
}
int main(){
int num = 40;
if(num <= 1){
cout<<"Wrong input";
}
else{
cout<<"Recursive program to print all numbers less than N which consist of digits 1 or 3 only are: ";
Recursive_Numbers(num);
}
return 0;
}
실행 결과
위 코드를 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.
Recursive program to print all numbers less than N which consist of digits 1 or 3 only are: 33 31 13 11 3 1
동작 원리 요약
이 프로그램의 핵심은 자릿수 분리와 재귀 감소입니다. 나눗셈 연산(temp % 10)을 통해 각 자릿수를 하나씩 추출하여 1 또는 3인지 검증하고, 조건을 만족하지 않는 순간 즉시 flag를 해제해 불필요한 연산을 줄입니다. 그런 다음 num을 1씩 감소시키며 스스로를 다시 호출함으로써, 1까지 모든 후보 수를 체계적으로 검사하게 됩니다. 다만 이 방식은 num부터 1까지 모든 수를 검사하므로 시간 복잡도는 O(N × 자릿수)이며, 입력 범위가 클 경우 백트래킹으로 1과 3의 조합만 생성하는 방식이 더 효율적일 수 있습니다.