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

오일러 프로젝트 44

오각수는 Pn = n (3n − 1)/2 라는 공식으로 구할 수 있고, 처음 10개의 오각수는 다음과 같습니다.

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …

위에서 P4 + P7 = 22 + 70 = 92 = P8이 됨을 볼 수 있습니다. 하지만 두 값의 차인 70 − 22 = 48 은 오각수가 아닙니다. 합과 차도 모두 오각수인 두 오각수 Pj, Pk 에 대해서, 그 차이 D = | Pk − Pj | 는 가장 작을 때 얼마입니까?

http://euler.synap.co.kr/prob_detail.php?id=44

접근

오각수의 일반항 공식은 n에 대한 2차식의 모양을 하고 있다. 바로 이웃한 오각수의 차이(Pn+1 – Pn)은 (6 * n + 1) / 2을 따른다. 비슷하게 k 만큼 떨어진 오각수의 차이(P(n+k) – P(n))는 (3(k + n)^2 - k - n^2) / 2로 계산된다. 즉 두 오각수의 차이는 작은 오각수가 작을수록, 그리고 두 오각수의 거리가 작을수록 작다. 따라서 일정한 영역 내의 오각수들 중에서 가장 작은 Pn, P(n – k)를 찾으면 되겠다.

이 접근 방식은 이전에 풀이했던 친화수의 쌍 찾는 문제와 비슷하게 접근한다고 보면된다. 대신에 여기서는 까다로운 상황이 하나 있다. 범위의 상한이 정해져있지 않은 것이다. 그래서 오각수의 집합을 미리 한정하기가 어렵다. 따라서 오각수의 집합을 그 크기를 늘려가면서 조건을 만족하는 오각수의 쌍을 찾아나가는 알고리듬이 필요하다.

  1. 먼저 크기가 n 인 정렬된 오각수의 리스트 A가 있다고 가정한다. (P1, P2, P3, … Pn을 원소로 한다.) 초기에는 10개 정도의 크기로 잡는다.
  2. 리스트 A에서 가장 큰 오각수의 바로 다음 오각수 값을 P(n+1)을 계산한다.
  3. A의 원소 중에서 큰 순서대로 s 를 골라서 t = P(n+1) – s 를 계산한다. 만약 t가 A의 원소라면, P(n+1)은 두 오각수 s, t의 합이다.
  4. 이 때 |t – s| 역시 A의 원소라면 합과 차가 모두 오각수인 쌍을 발견한 것이 된다.
  5. 만약 조건을 만족하는 s를 찾지 못한다면 P(n + 1)을 A에 추가하고 2로 돌아간다.

이 과정을 반복하여 처음 찾게 되는 값이 차이가 최소인 합과 차가 모두 오각수가 될 것이다.

%%time

def gen():
  k = 1
  while True:
    yield k * (3 * k - 1) // 2
    k += 1

g = gen()
ws = [next(g) for _ in range(10)]
ps = set(ws)
res, done = -1, False

while not done:
  p = next(g)
  for s in ws[::-1]:
    t = p - s
    if t in ps and abs(t - s) in ps:
      res = abs(t - s)
      done = True
      break
  else:
    ws.append(p)
    ps.add(p)

print(res)