C++에서 0을 홀수 개 포함하는 N자리 숫자의 개수 구하기

문제 개요

숫자 N이 입력으로 주어집니다. 목표는 0을 홀수 개 포함하는 모든 N자리 숫자의 개수를 구하는 것입니다. 단, 000과 같이 선행 0(앞자리 0)으로 시작하는 조합도 유효한 숫자로 간주합니다.

입력 및 출력 예시

입력: N = 3
출력: 244

설명: 가능한 3자리 숫자 조합은 아래와 같이 구성됩니다.

가장 작은 수는 000이며, 이어서 011, 012, 013, 014 … 형태로 진행되어 가장 큰 수는 990입니다.

입력: N = 5
출력: 33616

설명: 가능한 5자리 숫자 조합은 아래와 같이 구성됩니다.

가장 작은 수는 00000이며, 이어서 00011, 00012, 00013 … 형태로 진행되어 가장 큰 수는 99990입니다.

접근 방식

모든 숫자를 하나씩 확인하는 대신 수학적 성질을 활용하면 몇 번의 연산만으로 답을 구할 수 있습니다.

선행 0을 포함한 N자리 숫자는 총 10^N개입니다.
정확히 k개의 0을 포함하는 N자리 숫자의 개수는 C(N, k) × 9^N−k입니다. 0이 들어갈 자리를 k개 선택하고, 나머지 자리에는 1~9 중 하나를 배치하기 때문입니다.
이항정리를 적용하면 0이 짝수 개 포함된 숫자의 수는 (10^N + 8^N) / 2이고, 0이 홀수 개 포함된 숫자의 수는 (10^N − 8^N) / 2임을 알 수 있습니다.

구현 단계

정수 N을 입력받습니다.
count_odd(int N) 함수는 0이 홀수 개 포함된 N자리 숫자의 개수를 반환합니다.
전체 N자리 숫자의 개수를 total = pow(10, N)으로 계산합니다.
이항정리에 기반한 보조 값 even = pow(8, N)을 계산합니다.
홀수 개수는 odd = (total − even) / 2로 구합니다.
odd 값을 최종 결과로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

int count_odd(int N){
    int total = pow(10, N);   // 전체 N자리 숫자의 개수
    int even = pow(8, N);     // 이항정리 기반 보조 값
    int odd = (total - even) / 2;
    return odd;
}

int main(){
    int N = 4;
    cout << "0이 홀수 개 포함된 N자리 숫자의 개수: " << count_odd(N);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

0이 홀수 개 포함된 N자리 숫자의 개수: 2952

복잡도 분석

시간 복잡도는 거듭제곱 계산에 따라 O(log N) 수준이며, 반복문 없이 상수 개의 연산만 수행하므로 N이 커져도 매우 효율적으로 동작합니다.