오일러 프로젝트 56 번 문제는 큰 수의 자리수의 합에 관한 문제이다. 예전에 만들어 둔 BigNumber 를 이용하거나 하는 식으로 풀면 되는데, 파이썬의 경우에는 허무한 수준으로 간단하다.
구골(googol)은
을 일컫는 말로, 1뒤에 0이 백개나 붙는 어마어마한 수입니다.
은 1뒤에 0이 2백개나 붙으니 상상을 초월할만큼 크다 하겠습니다. 하지만 이 숫자들이 얼마나 크건간에, 각 자리수를 모두 합하면 둘 다 겨우 1밖에 되지 않습니다.
인 자연수
에 대해서, 자릿수의 합이 최대인 경우, 그 값은 얼마입니까?
접근
파이썬의 경우에는 원라이너로 해결된다. 거듭제곱한 결과를 문자열로 만들고 각 글자를 정수로 변환, 합산한 거 중에서 최대값이니까 다음과 같이 작성된다.
max((sum(c) for c in str(a**b)) for a in range(100) for b in range(100))Swift의 경우에는 예전에 만들어 둔 BigNumber 와 pow 함수를 써서 계산할 수 있다. 그럼에도 불구하고 시간이 너무 오래 걸린다….
do {
var result = 0
for x in 1..<100 {
let a = BigNumber(integer: x)
for b in 1..<100 {
let y = pow(a, b)
let z = y.description.characters.flatMap{ Int(String($0)) }.reduce(0, +)
if z > result { result = z }
}
}
print(result)
}시간을 좀 단축할 수 있는 방법을 생각해보자.
최적화 전략
우선 기본적으로 BigNumber 끼리의 곱셈이 수행 작업의 대부분이다. BigNumber의 곱셈 처리는 두 수를 이루는 각 항끼리의 조합을 모두 곱하여 더해 나가며 정리하는 방식으로 연산이 이루어진다. 따라서 항의 개수를 줄일 수 있으면 반복 횟수를 줄여서 조금은 계산량을 줄 일 수 있다.
항의 개수를 줄이기 위해서는 항 하나가 담을 수 있는 계수의 범위를 0~9,999 에서 0~999,999,999 정도로 늘릴 수 있다. 이렇게만 해도 계산 과정에서의 항의 총 수가 많이 줄어들게 된다. (999,999,999 ^ 2 는 2^63보다 작으므로 곱하기 연산에서 처리 가능하다.) 실제로 이렇게 처리하는 것은 약간의 성능 향상을 꾀할 수 있으나, 드라마틱한 시간 단축을 가져오지는 못했다.
문제에서 구하고자 하는 것은 자리수의 합의 최대값이다. 따라서 위 코드처럼 아래에서 위로 올라가는 것이 아니라 내려오면서 루프의 수를 줄일 수 있는 방법을 찾아보자.
예를 들어 지금까지 구한 자리 수의 최대값 A가 있고, 현재 계산된
for a in stride(from: 99, to:0, by:-1) {
let m = BigNumber(integer: a)
for b in stride(from: 99, to:0, by: -1) {
let n = pow(m, b).description
if n.count * 9 < result { break }
let k = n.description.flatMap{ Int(String($0)) }.reduce(0, +)
if result < k { result = k }
}
}이렇게 변경하는 경우 시행횟수는 약 1/3로 줄어들게 된다. (물론 앞에서 큰 값을 많이 계산하기 때문에 시간이 1/3로 단축되지는 않는다.)