선행 0이 없는 N자리 밑수 B 숫자의 개수 구하기

이번 글에서 다룰 문제는 다음과 같습니다. 자릿수 N과 밑수(base) B가 주어졌을 때, 선행 0(leading zero)이 없는 N자리 숫자가 총 몇 개인지 세는 것입니다.

예를 들어 N이 2이고 B가 2라고 가정해 보겠습니다. 이 경우 만들 수 있는 두 자리 값은 00, 01, 10, 11로 네 가지입니다. 하지만 선행 0이 없어야 한다는 조건을 만족하는 값은 10과 11뿐이므로, 유효한 숫자는 두 개입니다.

수학적 접근 방법

밑수가 B라면 사용할 수 있는 각 자리의 숫자는 0부터 B−1까지 총 B개입니다. 따라서 선행 0을 포함하여 만들 수 있는 N자리 값의 개수는 B^N개입니다.

여기서 첫 번째 자리가 0으로 시작하는 경우를 생각해 보면, 나머지 N−1자리만 자유롭게 채우면 되므로 그 개수는 B^N-1개입니다. 결국 선행 0이 없는 N자리 숫자의 총 개수는 다음 공식으로 구할 수 있습니다.

B^N − B^N-1

알고리즘

countNDigitNum(N, B)

Begin
    total := B^N
    with_zero := B^(N-1)
    return total - with_zero
End

C++ 구현 예제

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

int countNDigitNum(int N, int B) {
    int total = pow(B, N);
    int with_zero = pow(B, N - 1);
    return total - with_zero;
}

int main() {
    int N = 5;
    int B = 8;
    cout << "Number of values: " << countNDigitNum(N, B);
}

실행 결과

Number of values: 28672

위 예제에서 N=5, B=8일 때 결과는 28672입니다. 이는 8⁵(32768)에서 8⁴(4096)을 뺀 값으로, 선행 0이 없는 다섯 자리 팔진수의 개수와 정확히 일치합니다.