프로젝트 오일러 014

문제

14번 문제

백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은?

사이냅소프트

우박수

우박수 과정을 따라가는 알고리듬은 간단합니다. 짝수일 때는 절반으로 내려가고, 짝수 일 때는 3배 + 1로 올라갑니다.

def h(n):
  c = 1
  while n > 1:
    if n % 2 == 0:
      n = n // 2
    else:
      n = n * 3 + 1
    c += 1
  return c

백만 이하의 수에 대해서 가장 긴 우박수를 찾기 위해서는 모든 수를 추적해야하는데, 우박수 과정을 따라가는 것이 간단하더라도 이것을 백만번 반복하는 것은 또 다른 문제입니다.

문제에서 13은 10단계를 거쳐 1이 됩니다. 26은 어떻습니까? 26은 반으로 나누면 13인데, 13은 10단계를 거친다고 했으니, 26은 11단계를 거치게 된다는 사실을 금방 알 수 있습니다. 이건 미리 계산된 결과를 알고 있다면 굳이 다시 계산해볼 필요가 없다는 뜻이고, 메모이제이션으로 개선이 가능하다는 것을 의미합니다.

메모이제이션을 적용하기 위해서는 재귀 호출의 형태를 띄도록 우박수 추적 함수를 변형하는 것이 좋습니다.

from functools import wraps

def memoize(f):
  cache = {}

  @wraps(f)
  def inner(x):
    if x in cache:
      return cache[x]
    r = f(x)
    cache[x] = r
    return r

  return inner

@memoize
def hx(x):
  if x == 1:
    return 1
  if x % 2 == 0:
    return hx(x // 2) + 1
  return hx(x * 3 + 1) + 1

정렬하기

이 문제는 최대가 되는 단계의 수를 구하는 것이 아니라, 단계의 수가 최대인 값을 구하는 문제입니다. 보통 이런 경우에 for 루프를 돌면서 단계를 비교하고 그 때의 단계와, 값을 각각 기록하고 갱신하는 방식으로 코드를 작성하는 경우가 많은데요, 튜플을 이용해서 정렬하면 좀 더 간편하게 해결할 수 있습니다. 튜플을 정렬할 때에는 첫번째 요소를 기준으로 우선 정렬하고, 첫번째 요소가 같은 경우에는 두 번째 요소를 비교합니다.

따라서 hx(n)이 최대일 때의 n을 알고 싶다면, (hx(n), n) 의 최대값을 구한 다음, 두 번째 요소를 취하면 됩니다.

print(max((hx(n), n) for n in range(1, 100_0001))[1])