문제 개요
하나의 숫자 n이 주어졌을 때, 1부터 n 사이의 정수 중에서 각 자릿수가 오직 0과 1로만 구성된 숫자가 몇 개 있는지 찾는 것이 이번 문제의 목표입니다.
예를 들어 n = 15라면, 조건을 만족하는 수는 1, 10, 11로 총 3개입니다. 반면 2부터 9까지의 수와 12~15 사이의 수들은 0과 1 이외의 자릿수를 포함하므로 제외됩니다.
해결 접근 방식
이 문제는 재귀 함수를 이용해 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재 값 p에서 뒤에 0을 붙인 수(p × 10)와 뒤에 1을 붙인 수(p × 10 + 1)를 재귀적으로 생성합니다.
- p가 n보다 커지면 더 이상 유효한 숫자를 만들 수 없으므로 탐색을 중단하고 0을 반환합니다.
- 그렇지 않으면 현재 숫자 1개를 세고, 두 가지 분기에 대한 재귀 호출 결과를 모두 더해 반환합니다.
구현 예제
#include<iostream>
using namespace std;
int numberOfValues(int p, int n) {
if (p > n)
return 0;
return 1 + numberOfValues(p * 10, n) + numberOfValues(p * 10 + 1, n);
}
int main() {
int n = 120;
cout << "Number of values using 0s and 1s: " << numberOfValues(1, n);
}
실행 결과
Number of values using 0s and 1s: 7
동작 원리 분석
n = 120일 때 함수는 다음과 같은 순서로 유효한 숫자들을 발견합니다.
1 → 10 → 11 → 100 → 101 → 110 → 111
총 7개의 숫자가 120 이하이면서 0과 1로만 이루어져 있으므로 결과값은 7이 됩니다. 반면 111에 0 또는 1을 붙인 1110, 1111은 n보다 크기 때문에 탐색 대상에서 제외됩니다.
시간 복잡도
각 단계마다 숫자를 2개씩 생성하므로 전체 탐색 트리의 깊이는 n의 자릿수 d에 비례하며, 시간 복잡도는 대략 O(d) 수준의 재귀 깊이와 최대 2d+1개의 노드 방문으로 표현할 수 있습니다. 일반적인 정수 범위에서 매우 효율적으로 동작합니다.