프로젝트 오일러 040

접근

문제에서는 012345678910111213141516···과 같이 숫자를 계속해서 이어 써 나갈 때 앞에서 10의 0~7 거듭제곱 번째에 해당하는 숫자들의 누적곱을 구하면 됩니다.

1, 2, 3, ···, 11, 12와 같이 진행하는 정수를 n이라고 하고, 숫자의 순서를 인덱스(idx)라고 합시다. n이 1씩 증가할 때, n의 마지막 자리 숫자의 인덱스는 n의 자리 수(상용로그로 알 수 있죠)만큼 증가하게 됩니다. 그리고 문제에서 요구하는 숫자들의 인덱스는 10의 0~6 거듭제곱에 해당하는 값입니다. 이 거듭제곱의 수를 step이라고 하겠습니다.

n이 증가함에 따라 idx는 같이 증가하지만, 항상 n의 마지막 숫자의 idx가 10의 거듭제곱에 일치하지는 않습니다. 따라서 idx값을 자리수 만큼 늘려가다가 목표 인덱스를 넘어서는 숫자가 나온다면, $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())

제너레이터

사실 이 문제는 파이썬에서는 ‘제너레이터’를 이용하면 좀 더 간단해집니다. 수열을 생성하는 원리가 간단하다고 했으니, 수열을 생성해주는 제너레이터를 돌려서 필요한 숫자들만 취하면 되는 것이죠. 대신 정직하게 100만번의 루프를 돌기 때문에 시간은 조금 더 걸릴 수 있습니다.

def champ():
    i, j = 1, 1
    while True:
        for c in str(i):
            yield (j, int(c))
            j += 1
        i += 1

def main():
    k = 0
    res = 1
    for (x, y) in champ():
        if x == 10**k:
            res *= y
            k += 1
            if k > 6:
                break
    print(res)

main()