오일러 프로젝트 56

오일러 프로젝트 56 번 문제는 큰 수의 자리수의 합에 관한 문제이다. 예전에 만들어 둔 BigNumber 를 이용하거나 하는 식으로 풀면 되는데, 파이썬의 경우에는 허무한 수준으로 간단하다.

구골(googol)은 10^{100}을 일컫는 말로, 1뒤에 0이 백개나 붙는 어마어마한 수입니다. 100^{100}은 1뒤에 0이 2백개나 붙으니 상상을 초월할만큼 크다 하겠습니다. 하지만 이 숫자들이 얼마나 크건간에, 각 자리수를 모두 합하면 둘 다 겨우 1밖에 되지 않습니다. a, b < 100인 자연수 a^b에 대해서, 자릿수의 합이 최대인 경우, 그 값은 얼마입니까?

접근

파이썬의 경우에는 원라이너로 해결된다. 거듭제곱한 결과를 문자열로 만들고 각 글자를 정수로 변환, 합산한 거 중에서 최대값이니까 다음과 같이 작성된다.

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가 있고, 현재 계산된 a^b의 값이 있다고 하자. 계산된 값의 자리수에서 합이 최대가 될 수 있는 상황은 모든 자리 숫자가 9일 때이다. b가 작아지는 중이므로, 자리수 * 9 한 값이 A보다 작다면 그 이하의 b에 대해서는 계산할 필요가 없을 것이다.  따라서 다음과 같이 로직을 수정한다.

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로 단축되지는 않는다.)