프로젝트 오일러 030
문제
사이냅소프트
각 자리 수를 5제곱하기
우선 편의상 '각 자리 숫자를 제곱하여 그 합을 구하는 연산'을 "만두빚기"라고 부르기로 약속하겠습니다. (이름은 중요하지 않으니 자기가 원하는 이름을 붙여도 됩니다.)
한자리 수에서 만두빚기를 했을 때 한 자리 수가 되는 것은 1이 유일합니다. 한 자리 수 중에서 가장 큰 9는 만두빚기를 하면 59,049가 됩니다. 모든 숫자가 9로 이루어진 두 자리, 세 자리 숫자들은 만두빚기의 결과가 59,049의 배수가 될 것입니다. 그리고 만두빚기의 결과는 극적으로 커지는 것 같지만, 일정 값 이상부터는 증가폭이 그리 크지 않습니다. 자릿수가 늘어날 때마다 최대 59,049만큼만 더 커질 수 있기 때문에, 종국에는 자리 수로 증가로 인한 원래 값의 증가를 따라가지 못하게 됩니다.
- mandoo(99) = 59,049 × 2 = 118,098
- mandoo(999) = 59,049 × 3 = 177,147
- mandoo(9,999) = 59,049 × 4 = 236,196
- mandoo(99,999) = 59,049 × 5 = 354,294
- mandoo(999,999) = 59,049 × 6 = 354,294
- mandoo(9,999,999) = 59,049 × 7 = 413,343
7자리부터는 만두 빚기의 이론적 최대 값이 413,343에 불과하기 때문에 만두빚기의 결과가 자기자신과 같은 숫자들은 1백만 이하에 있습니다. 1백만 이하라면 루프를 돌면서 처리해봄즉한 범위입니다.
def mandoo(n: int):
return sum(int(x) ** 5 for x in str(n))
print(sum(x for x in range(10, 100_0000) if mandoo(x) == x))PC 성능에 따라 다르겠지만, 제 오랜 PC에서는 2초가 넘게 걸리는 군요. 성능을 조금 더 개선하려면 1)범위를 축소하거나, 2) 같은 연산을 반복하지 않도록 하는 방법을 생각해 볼 수 있겠습니다. 위 코드에서는 다섯 제곱을 엄청 많이 반복하는데, 0~9사이의 값에 대해서만 다섯제곱을 하고 있으므로, 이 값을 캐싱해두면 좀 더 낫지 않을까요?
s5 = tuple(i ** 5 for i in range(10))
def mandoo(n: int):
return sum(s5[int(x)] for x in str(n))
print(sum(x for x in range(10, 100_0000) if mandoo(x) == x))
결과는 어느 정도 성공적입니다. 대신에 반복 횟수를 줄여서 더 적은 루프를 돌 수 있을까요? 그건 조금 어려워보입니다. 예를 들어 숫자 3의 다섯제곱은 이미 세 자리이므로, 3이 포함된다면 한자리나 두자리 수에서는 답이 될 수 없습니다. 즉 0, 1, 2로만 이루어진 조합에서만 답이 나올 수 있습니다. 비슷하게 4자리 수에서는 1부터 6까지의 숫자로만 구성되어야 합니다. 그렇지만 이러한 비교를 위해서 준비해야하는 과정이 길어지면 전체 성능에서는 손해를 볼 수 있어서 생략했습니다.
