프로젝트 오일러 040

문제

40번 문제

어떤 무리수에서 소수점 <var>n</var>번째 자리 숫자 알아내기

사이냅소프트

접근

문제에서는 012345678910111213141516···과 같이 숫자를 계속해서 이어 써 나갈 때 앞에서 10⁰ 번째, 10¹ 번째, ··· 10⁷ 번째 숫자를 각각 찾아서 그 곱을 구하는 문제입니다. 느끼기에는 단순한 문제처럼도 보입니다. 이 숫자들의 배열이 진행하는 규칙은 단순하지만, 일반항을 찾기는 어렵습니다. 앞에서부터 따라가는 게 좋을 것 같습니다.

1, 2, 3, ···, 11, 12와 같이 진행하는 정수를 n이라고 하고, 숫자의 순서를 인덱스(idx)라고 합시다. n이 1씩 증가할 때, n의 마지막 자리 숫자의 인덱스는 n의 자리 수 만큼 증가하게 됩니다.

그리고 문제에서 요구하는 숫자들의 인덱스는 10의 0~7 거듭제곱에 해당하는 값입니다. 이 거듭제곱의 수를 step이라고 하겠습니다.

n이 증가함에 따라 idx는 같이 증가하지만, 항상 n의 끝자리 숫자의 idx가 10^a에 일치하지는 않습니다. 만약 그 값을 초과했다면 그 값에 해당하는 숫자는 숫자를 문자열로 바꾼 후 (10^step - idx - 1)의 인덱스로 해당 숫자를 찾을 수 있습니다. (곰곰히 생각해봅시다.)

from math import log10

@elapesd
def main():
    res, idx, n, step = 1, 0, 1, 0
    while step > 6:
        idx += int(log10(n) + 1)
        if idx >= 10**step:
            res *= int(str(n)[10**step - idx - 1])
            step += 1
        n += 1
    return res

if __name__ == '__main__':
    print(main())

제너레이터

사실 이 문제는 파이썬에서는 '제너레이터'를 이용하면 좀 더 간단해집니다. 수열을 생성하는 원리가 간단하다고 했으니, 수열을 생성해주는 제너레이터를 돌려서 필요한 숫자들만 취하면 되는 것이죠.

def g():
    n = 0
    while True:
        for c in str(n):
            yield c
        n += 1


@elapsed
def main2():
    step, limit = 1, 6
    res = 1
    for i, x in enumerate(g()):
        if i == 10**step:
            res *= int(x)
            step += 1
            if step > limit:
                break
    return res

오래 전에 풀어보고 썼던 글들에서 문제를 다시 풀어보고 다시 글을 발행하다보니 어느새 40번까지 달려왔네요. 아직까지는 크게 어렵다거나, 파이썬으로 풀기에는 성능을 내기 어렵거나 하는 문제는 크게 없었던 것 같습니다. 그럼 다음 글에서 만나겠습니다.