C++로 0을 포함하는 d자리 양의 정수 개수 구하기

이 튜토리얼에서는 0을 자릿수 중 하나로 포함하는 d자리 양의 정수의 개수를 구하는 프로그램을 C++로 작성하는 방법을 알아봅니다.

문제 이해하기

숫자 d가 하나 주어졌을 때, d자리 양의 정수 전체 중에서 0을 적어도 하나 포함하고 있는 수의 개수를 세어 출력하는 것이 목표입니다.

예를 들어 d = 2인 경우를 생각해 보겠습니다. 두 자리 양의 정수는 10부터 99까지 총 90개이며, 이 가운데 0을 포함하지 않는 수는 11, 12, ..., 99처럼 81개입니다. 따라서 0을 포함하는 수는 90 − 81 = 9개(10, 20, 30, ..., 90)가 됩니다.

접근 방법

모든 수를 일일이 확인하는 대신, 간단한 조합론적 계산으로 답을 바로 구할 수 있습니다.

d자리 양의 정수의 총 개수: 첫 자리는 1~9(9가지), 나머지 자리는 0~9(10가지)이므로 9 × 10^d−1개
0을 하나도 포함하지 않는 d자리 수의 개수: 모든 자리가 1~9만 가능하므로 9^d개
따라서 0을 포함하는 d자리 수의 개수는 9 × 10^d−1 − 9^d = 9 × (10^d−1 − 9^d−1)

C++ 구현 예시

#include<bits/stdc++.h>
using namespace std;
// 0을 포함하는 d자리 숫자의 개수를 계산하는 함수
int count_num(int d) {
    return 9*(pow(10,d-1) - pow(9,d-1));
}
int main(){
    int d = 1;
    cout << count_num(d) << endl;
    d = 2;
    cout << count_num(d) << endl;
    d = 4;
    cout << count_num(d) << endl;
    return 0;
}

출력 결과

0
9
2439

코드 설명

count_num() 함수는 위에서 유도한 공식 9 × (10^d−1 − 9^d−1)을 그대로 구현한 것입니다.

d = 1: 한 자리 양의 정수(1~9)에는 0이 들어갈 수 없으므로 0개
d = 2: 10, 20, 30, ..., 90으로 총 9개
d = 4: 네 자리 수 9,000개 중 0이 없는 수 6,561개를 제외한 2,439개