[Python] 프로젝트오일러 #80 제곱근 확장(수학)

이번 문제는 난이도 20%입니다.

 

사실 이 문제의 뜻을 정확하게 파악하는데 좀 문제가 있습니다.   영어권 사용자들에게도 헷갈리는 문제이기도 하죠.

 

https://projecteuler.net/problem=80

 

일단 중요한 것은 이 문제를 풀기 위해서는 큰 정수 계산을 할 수 있거나, 높은 정밀도의 실수 연산이 필요합니다.  이미 알고있는 32비트 실수형이나 64비트 실수형은 정밀도가 그렇게 높지 않습니다.  32비트 실수형은 유효자리수가 6자리정도이고, 64비트 실수형은 유효자리수가 15자리 정도입니다.  그런데 이 프로그램은 100자리 이상의 유효자리수를 요구합니다.

 

 

일단 문제를 해석하면,

\(\sqrt{2}\)와 같은 자연수의 제곱근은 무한소수로 표현됩니다.  \( \sqrt{2} = 1.4142135623730950488016887... \) 가 되는데요.  이렇게 무한소수로 표현되는 수의 첫번째 100개의 수의 합을 구하면 475가 됩니다. 

 

\[1 + 4 + 1 + 4 + 2 + ... + 2 = 475 \]

 

3에 대한 것은 441이 되고요.  4는 제곱근을 구하면 무한소수가 되지 않기 때문에 건너띕니다.

 

그래서 1부터 100까지의 자연수 중 제곱근이 무한소수가 되는 수에 한해서 무한소수에서 표현되는 첫 100개의 수의 합을 모두 구해서 합하는 것이 문제입니다.

 

전 파이썬에서 제공하는 Decimal을 이용했습니다.  이 모듈을 이용하면, 사실 실제 프로그램할 것은 문자열 처리밖에 남지 않습니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

from decimal import *

def getdigitsum(d):
    r = str(Decimal(d).sqrt())
    if len(r) < 100: return 0
    s = 0
    for c in r[:101]:
        if c != '.': s += int(c)
    return s

getcontext().prec = 110
s = 0
for d in range(2, 100): s += getdigitsum(d)
print(f'Ans = {s}')