오일러 프로젝트 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)

접근

오각수의 일반항인 Pn은 n에 대한 이차식의 모양을 하고 있다. 따라서 n 이 커지면 커질 수록 P_n - P_{n-1}이 커지게 된다. 따라서 오각수의 수열 Pn에 대해 합과 차가 모두 오각수가 되는 조건을 만족하는 순서쌍을 (P_i, P_j) (i < j)라 할 때, 두 값의 차이가 최소가 된다는 것은 P_j가 최소가 되어야 한다는 점에 착안한다.

문제는 이 값이 언제쯤 나타날 것인지에 대한 정보는 직접적으로 주어지지 않았다는 점이다. 따라서 특정한 크기의 오각수 집합을 미리 만들어 놓고 사용할 수는 없다.

따라서 다음과 같은 알고리듬으로 진행한다.

  1. 조건을 만족하지 못하는 정렬된 오각수의 리스트가 있다고 가정한다.  (k = 1, 2, 3, … n – 1)
  2. 1.의 리스트의 가장 큰 오각수 바로 다음 번 오각수 Pn을 생성한다.
  3. 두 오각수의 합이 Pn이 된다고 가정하면, 1.의 리스트 중 p와 s의 합이 Pn이 될 것이다. (p + s == Pn)
  4. 따라서 1.의 리스트에서 임의의 원소 p를 뽑고, s = Pn – p 로 계산한다. 만약 s가 1.의 원소라면 합의 조건은 만족한다.
  5. 두 오각수 p, s에 대해서 차이인 d를 계산한다. 같은 방식으로 1.의 리스트에 d가 포함된다면 모든 조건이 만족된다.

따라서 새로 추가되는 오각수가 Pj , Pi 라는 점에 방점을 찍지 않고 이전 시행에서 만들어진 연속 오각수 리스트로부터 답을 찾을 수 있는지를 검사한다. 조금 돌아가는 느낌이기는 하지만, 아주 빠르게 답을 찾을 수 있다.

참고로 리스트를 통해서 “정렬된” 오각수 리스트를 관리하면서, 동시에 순서없는 집합을 이용해서 오각수여부 판별을 빠르게 처리하는 것이 성능 개선의 팁이라 할 수 있다.

 

def make_pent(k):
  return k * (k * 3 - 1) // 2

def main():
  pents = [make_pent(x) for x in range(1, 4)]
  sieve = set(pends)
  k = 4
  while True:
    pn = make_pent(k)
    for p in pents:
      s = pn - p
      d = abs(p - s)
      ## s와 p의 합이 오각수(pn)이려면, s도 오각수여야
      ## 하고, 두 수의 차인 d 역시 오각수여야 한다.
      if s in sieve and d in sieve: 
        print(d)
        return
    ## 새로운 pn을 오각수 집합에 추가하고, 다음 오각수를 향해서 진행
    pents.append(pn)
    sieve.add(pn)
    k += 1
      
%time main()
## 실행시간 1초 미만

Swift 풀이

Swift 코드 역시 대동소이하다.

fun make_penta(_ k: Int) -> Int = { return k * (k * 3 - 1) / }

main: do {
  var a = (1...3).map(make_penta)
  var b = Set(a)
  var k = 4
  while true {
    let pn = make_penta(k)
    for p in a {
      if case let s = pn - p, case let d = abs(s - p),
      b.contains(s), b.contains(d) {
        print(d)
        break main
      }
    }
    a.append(pn); b.insert(pn)
    k += 1
  }
}