[Project Euler] 40. 어떤 무리수에서 소수점 n번째 자리 숫자 알아내기

40. 어떤 무리수에서 소수점 n번째 자리 숫자 알아내기

소수점 뒤에 양의 정수를 차례대로 붙여 나가면 아래와 같은 무리수를 만들 수 있습니다.



0.123456789101112131415161718192021... 이 무리수의 소수점 아래 12번째 자리에는 1이 옵니다 (위에서 붉게 표시된 숫자). 소수점 아래 n번째 숫자를 dn이라고 했을 때, 아래 식의 값은 얼마입니까? d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000

Click
먼저 n번째 위치한 수가 포함된 수를 찾고 해당 수에서 몇번째 수를 가르키는 지를 찾으면 dn의 값을 쉽게 구할 수 있습니다.

그러기위해서는 우선 k자릿수의 수가 소수에서 몇개의 자리를 차지하는지부터 접근을 시작해 보는게 빠를 것입니다.

1자리 수는 1~9까지 9개.
2자리 수는 10~99까지 90개.
3자리 수는 100~999까지 900개.
....

각 k 자릿수의 수는 9*10^(k-1)개 그리고 이 각 자릿수가 이루고 있는 문자는

1자릿수가 9*1 개
2자릿수가 90*2 개
3자릿수가 900*3 개
....

각 k 자릿수의 수가 9*10^(k-1) * k 개가 된다.

k를 1부터 증가시켜가며 9*10^(k-1) * k보다 작은지 확인하여
작지 않으면 n에서 9*10^(k-1) * k 를 빼가며

해당 9*10^(k-1) * k보다 작은 수를 찾으면 자릿수 n번째 수가 가리키는 수의 자릿수 k를 찾을 수 있다.

그리고 마지막 남은 temp = n - ∑9*10^(k-1) 의 값(∑의 i범위는 0~(k-1))을 k로 나누면 어떤 값의 일부인지를 알 수 있고, number = (temp-1)/k + 10^(k-1)
다시 temp값을 k로 나눈 나머지 값은 해당 값의 몇번째 값인지를 알 수 있다. digit = k-(temp-1)%k

최종으로 number에서 digit번째의 수를 찾기 위해서는 (number/10^(digit-1))%10을 해주면 된다.

위와 같이 구하면 쉽게 구할 수 있겠네요.
여기에 9*10^(k-1) * k 를 쉽게 구하기 위해 t=9에서 자릿수 증가시마다 10을 곱해주는 방법으로 구현 하였습니다.

<script language="Javascript" type="text/javascript">
function func040(n){
    var temp = n;
    var t = 9;
    var k=1;
    for(; temp>=t*k; k++){
        temp -= t*k;
        t *= 10;
    }
    
    return parseInt((((temp-1)/k+t/9)/Math.pow(10,k-(temp-1)%k-1))%10);
}
function p040(){
    var r = 1;
    for(var d=1; d<=1000000; d*=10)
        r *= func040(d);
    alert(r);
}
</script>