챔퍼나운(Champernowne) 상수의 특정 자리 숫자는? (프로젝트 오일러 #40)

정규수(Normal number)라는 개념이 있다.

그리고, 극단적인 정규수로 챔퍼나운 상수(Champernowne's constant)가 있다.

이 문제는 챔퍼나운 상수의 1, 10, 100, 1000, 10000, 100000, 1000000 자리 숫자의 곱을 구하는 문제다.

근데, 정규수와 챔퍼나운 상수의 수학적 의미와 별개로 이 문제는 숫자만 나열하면 되는 문제라 의외로 쉽다.

처음부터 일일이 다 늘어놓는 방법도 있지만, 그건 좀 심하고, 조금만 생각을 해보면 계산을 많이 줄일 수 있다.

1. 1~9자리는 그대로 1~9임

2. 10~99의 90개는 2자리임

3. 100~999의 900개는 3자리임, 이후도 같은 규칙임

이런 규칙들을 염두에 두면 대략 아래와 같은 코드가 나온다.

#include <cstdio>
#include <cmath>

unsigned nDigitBegin(unsigned digit)
{
    unsigned count = 1;
    for (unsigned i = 1; i < digit; i++) {
        count *= 10;
    }
    return count;
}

unsigned getNthDigit(unsigned n)
{
    if (n < 10) return n;
    // 1~9 : 1자리
    // 10~99: 2자리 (90개)
    // 100~999: 3자리 (900개)

    // 이 sum은 자리수의 합을 의미함. 숫자의 합이 아님
    unsigned sum = 9;
    unsigned digit = 1;
    while (sum < n) {
        digit++;
        sum += digit * 9 * nDigitBegin(digit);
    }

    // 결과는 digit 자리 내에 있음
    // 한 자리 백
    sum -= digit * 9 * nDigitBegin(digit);
    // 현재까지의 자리수의 합은 sum

    unsigned from = nDigitBegin(digit);
    // 숫자는 from 부터 시작함

    int count = (n - sum - 1) / digit;
    // 현재부터 count개 다음에 시작된다는 뜻임

    sum += digit*count;
    from += count;

    static char str[10];
    sprintf_s(str, 10, "%u", from);

    return (str[n-sum-1]-'0');
}

int main(int argc, char* argv[])
{
    printf("-= Champernowne's constant =-\n");
    unsigned product = 1;
    for (unsigned i = 0, digit = 1; i < 7; i++, digit *= 10) {
        unsigned nthDigit = getNthDigit(digit);
        printf("d(%u) = %u\n", digit, nthDigit);
        product *= nthDigit;
    }
    printf("product = %u\n", product);
    return 0;
}

결과는 아래와 같다.

-= Champernowne's constant =-
d(1) = 1
d(10) = 1
d(100) = 5
d(1000) = 3
d(10000) = 7
d(100000) = 2
d(1000000) = 1
product = 210