콘텐츠로 건너뛰기
Home » 오일러 프로젝트 61

오일러 프로젝트 61

삼각수, 사각수, 오각수 같은 다각수들은 아래의 공식으로 만들 수 있습니다.

  • 삼각수 – P3n = n * ( n + 1) / 2 >> 1, 3, 5, 10, 15, …
  • 사각수 – P4n = n * n >> 1, 4, 9, 16, 25, …
  • 오각수 – P5n = (n * ( n * 3 – 1)) / 2 > 1, 5, 12, 22, 35, …
  • 육각수 – P6n = (n * (n * 2 – 1)) > 1, 6, 15, 28, 45, …
  • 칠각수 – P7n = ((n * (n * 5 – 3)) / 2 > 1, 7, 18, 34, 55, …
  • 팔각수 – P8n = n * (n * 3 – 2) > 1, 8, 21, 40, 65, …

그런데 4자리 숫자 8128, 2882, 8281 (순서대로 각각 3, 5, 4각수)에는 재미있는 성질이 있습니다. 먼저 각 숫자들은 두 자리씩 꼬리를 물고 진행합니다. 그리고 각 숫자들은 모두 서로 다른 다각수입니다. 이런 성질을 갖는 네자리 숫자 세 개는 이들이 유일합니다. 이렇게 순환하면서 서로 다른 다각수가 되는 4자리 숫자 여섯개의 유일한 순서쌍을 찾고 그 합을 구하세요.

두 네자리 수 a, b 가 꼬리를 문다는 것은 a를 100으로 나눈 나머지와, b를 100으로 나눈 몫이 서로 같다는 것이다. 네 자리 다각수 전체의 집합이 있다면, 이 조건을 사용해서 각각의 다각수에서 꼬리를 물 수 있는 다각수들을 연결하는 맵을 작성하는 일은 간단하다. 그리고 네 자리 다각수를 전부 구해도 그 수가 그리 많지 않을 것이기 때문에 빠르게 끝날 것으로 예상된다. 연결을 만들 수 있는 맵만 만든다면 그 이후의 일은 간단하다. 임의의 한 수로부터 연결 가능한 다각수 5개를 더 찾은 다음, 마지막 다각수로부터 첫번째 다각수가 다시 연결될 수 있는지를 검사하면 된다. 문제에서는 순환고리를 만들 수 있는 다각수의 순서쌍은 유일하다고 했으니, 첫번째로 조건을 만족하는 집합을 찾으면 된다.

중간에 더 이상 다른 다각수를 찾을 수 없다면 거슬러 올라가서 다음 수로 시도해보아야 한다. 이러한 흐름은 백트래킹으로 구현하는데, 파이썬에서 백트래킹을 구현하는 가장 간단한 방법은 yield from 구문을 사용해서 제너레이터의 위임 구조를 재귀적으로 만드는 것이다. 이 블로그에서 순열, 조합을 제너레이터를 사용하여 구현하는 방법을 소개한 적이 있는데, 그 글에서도 같은 방식을 사용했고 코드가 놀라울 수준으로 간단해지는 것을 확인할 수 있다.

전체 다각수 집합 및 연결 맵 만들기

사실 모든 육각수는 삼각수이기도 하므로, 각각의 다각수에는 이 수가 어떤 n각수인지를 구분하는 정보가 필요하다. 이 두 가지 정보를 튜플로 묶어서 생성 가능한 전체 다각수를 만들어 보자.

from typing import Generator

def gen() -> Generator[tuple[int, int], None, None]:
  equations = [
    lambda n: (n * (n + 1)) // 2,
    lambda n: n ** 2, 
    lambda n: (n * (3 * n - 1)) // 2, 
    lambda n: n * (2 * n - 1),
    lambda n: (n * (5 * n - 3)) // 2, 
    lambda n: n * (n * 3 - 2)
  ]
  for i, eq in enumerate(equations):
    k = 1
    while True:
      x = eq(k)
      if 999 < x <= 9999:
        yield (i + 3, x)
      elif x > 9999:
        break
      k += 1

numbers = list(gen())

전체 다각수 집합을 만들었으니, 이제 각 다각수에 대해서 연결 가능한 다각수의 집합을 구성해보자. 이것도 간단하다. 아래 예와 달리 for 루프를 돌면서 리스트에 append 할 수도 있겠지만, 이게 더 빠를 것이다.

links = {x:[y for y in numbers if x[0] != y[0] and x[1] % 100 == y[1] // 100]
         for x in numbers}

백트래킹으로 순서쌍 찾기

이제 연결되는 순서쌍을 구하는 핵심 로직을 구현한다.

def helper(
    d: dict[tuple[int, int], list[tuple[int, int]]],  # 링크 맵
    acc: list[tuple[int, int]],                       # 현단계까지 모인 순서쌍
    n: tuple[int, int],                               # 이번 단계의 값
    k: int                                            # 재귀 깊이
    ) -> list[tuple[int, int]]:
  
  if k == 1:
    # n 이 여섯번째 다각수인 경우 첫번째 다각수와 연결되는지 확인
    if acc[0][1] % 100 == n[1] // 100:
      yield [*acc, n]

    for m in d.get(n, []):
      # m이 이미 추가된 다각수 유형인지 확인
      if m[0] in [a[0] for a in acc]:
        continue
      yield from helper(d, [*acc, n], m, k-1)

yield from 을 사용하면 리턴해줄 값이 없는 경우는 자동으로 무시되기 때문에 백트래킹 로직을 구현하는 것이 매우 간편해짐을 알 수 있다. 참고로 이중 for 루프를 탈출하려 할 때 아래 테크닉을 참고해두면 좋다. 내부의 루프가 break로 중단되는 경우 else: 절이 실행되지 않기 때문에, else:continue 를 쓰고 바로 뒤에서 브레이크를 걸면 내부 루프가 break로 중단되면 바깥쪽 루프도 같이 중단된다.

for num in numbers:
  for xs in helper(links, [], num, 6):
    print(sum(x[1] for x in xs))
    break
  else:
    continue
  break