C++로 풀어보기: 숫자 3과 4만 사용해 만들 수 있는 길이 N 이하의 숫자 개수 구하기

숫자 N이 주어졌을 때, 오직 숫자 3과 4만 사용하여 만들 수 있는 모든 숫자의 개수를 구하는 문제입니다. 예를 들어 N = 2라면 만들 수 있는 숫자는 3, 4, 33, 34, 43, 44로 총 6개입니다.

접근 방법

규칙을 자세히 살펴보면 간단한 패턴을 발견할 수 있습니다.

• 한 자리 숫자(길이 1): 3, 4 → 총 2개 (2¹)
• 두 자리 숫자(길이 2): 33, 34, 43, 44 → 총 4개 (2²)
• 세 자리 숫자(길이 3): 333, 334, 343, 344, 433, 434, 443, 444 → 총 8개 (2³)

즉, 길이가 m인 숫자의 경우 각 자리마다 3 또는 4를 선택할 수 있으므로 2^m개의 조합이 존재합니다.

따라서 길이가 최대 N까지인 모든 숫자의 개수는 다음과 같은 등비수열의 합으로 계산할 수 있습니다.

2¹ + 2² + ... + 2ᴺ = 2^(N+1) − 2

예제 코드

#include<iostream>
#include<cmath>
using namespace std;

long long countNumbers(int n) {
    return (long long)(pow(2, n + 1)) - 2;
}

int main() {
    int n = 3;
    cout << "Number of values: " << countNumbers(n);
}

실행 결과

Number of values: 14

결과 분석

N = 3일 때 결과는 14입니다. 실제로 확인해 보면 한 자리 숫자 2개(3, 4) + 두 자리 숫자 4개 + 세 자리 숫자 8개 = 14개로, 공식 2⁴ − 2 = 14와 일치합니다.

복잡도 분석

• 시간 복잡도: O(log N) — 거듭제곱 계산에 소요되는 시간
• 공간 복잡도: O(1) — 추가 메모리 불필요

이처럼 규칙성을 파악하면 반복문 없이 하나의 수식으로 문제를 해결할 수 있어 매우 효율적입니다.