40. 프로젝트 오일러 #40 : 챔퍼나운 수

챔퍼나운수는 수론에서 무리수이자 초월수인 상수를 정의한 것입니다.  십진법이라면, 1, 2, 3, 4, 5, ... 를 세듯이 소수점 이하에 배열을 한 것입니다.

10진법 챔퍼나운 수는 다음과 같습니다.

이번 프로젝트 오일러 문제는 챔퍼나운 수의 소수점 아래 k번째 숫자를 계산하는 것입니다.  문제 자체가 소수점 아래 백만번째 숫자를 물어보는 것만큼, 챔퍼나운 수를 생성해서 표현하는 것은 의미가 없습니다.  사실 현재 컴퓨터에서 사용하는 어떤 자료형을 사용하더라도 소수점 이하 백만번째 숫자를 표현할 수 있지는 않습니다.  백만 자리의 숫자는 3백3십만비트 이상을 사용해야 하죠. 바이트로 따지면 4십만바이트정도가 필요합니다.

수식으로 바로 계산할 수도 있겠지만, 그것을 계산하기보다는 제 경우에는 for 루프를 이용했습니다.  수식으로 바로 계산할 수도 있겠지만, 그러기에는 좀 복잡합니다.

n이란 숫자가 주어지면, n을 소비하기 시작합니다.  일자리숫자는 하나의 수씩만 소모하므로 n이 9보다 크다면 9를 소모하고, 이제 세야할 숫자는 10이 됩니다.  10부터 99까지는 두자리 숫자씩 소모하므로 2x90 보다 n이 크다면, 2x90를 소모하고 이제 세야할 수는 100이 됩니다.

이런 식으로 계산을 하면, 자연스럽게 해당 자릿수를 알 수 있습니다.

그렇게 해서 GetDigit(int n)이란 함수를 작성하면 다음과 같습니다.

int GetDigit(int n)
{
    int s = 9;
    int t = 0;
    n--;
    for( int k = 1 ; ; k++ )
    {
        if( n >= s*k ) { n -= s*k; t += s; s *= 10; continue; }
        t += n/k+1;
        k -= n%k + 1;
        for( ; k ; t/=10, k-- ) ;
        return t%10;
    }
    return 0;
}

k란 변수는 현재 빼야할 숫자의 자릿수가 얼마인가입니다.  이 숫자는 1부터 시작하겠죠.  s 변수는 k 자릿수의 갯수가 몇개인가입니다.  처음 단자리 숫자는 총 9개입니다.  다음 두자리 숫자는 90개이죠.  그래서 소모되는 자릿수는 s*k 가 됩니다.  세자리 숫자들의 갯수는 900개입니다.  이와 같은 방식으로 원하는 자릿수 근처가 되면, 즉 s*k 보다 n이 작으면, 더이상 빼지 않고, 이제 실제 숫자를 얻기 위해서 해당 숫자의 위치를 찾습니다.  n을 k로 나누면 몇번째 숫자인지 알 수가 있습니다.