프로젝트 오일러 95 @ntalbs' stuff

1백만 이하의 숫자로 이루어진 친화고리
문제 자세히 보기: [국어] [영어]

주어진 정수의 진약수 합을 구하는 맵이 있으면 문제를 쉽게 풀 수 있을 것 같다. 문제 21에서 진약수의 합을 구하는 몇 가지 방법을 살펴보았지만 이 문제를 푸는 데 활용할 만큼 빠르지 않다. 그냥 다음과 같이 루프를 돌면서 맵을 만드는 게 나을 것 같다.

(def limit 1000000)

(def n->sod
  (->> (for [i (range 1 (/ limit 2))
             j (range (* 2 i) limit i)]
         [j i])
       (group-by first)
       (map (fn [[k v]] [k (map second v)]))
       (map (fn [[k v]] [k (apply + v)]))
       (into {})))

맵을 만들었다면 체인을 구하는 함수는 다음과 같이 작성할 수 있다.

(defn find-chain [n]
  (loop [n n s #{} acc []]
    (if-not (contains? s n)
      (recur (n->sod n) (conj s n) (conj acc n))
      (if (or (nil? (last acc)) (not= n (first acc))) nil acc))))

가장 긴 체인은 다음과 같이 구하면 된다.

(defn longest-chain [limit]
  (->> (range 2 (inc limit))
       (map find-chain)
       (remove nil?)
       (apply max-key count)))

다음과 같이 가장 긴 체인을 구한 다음 그 중 가장 작은 수를 찾으면 문제의 답이다.

(defn solve []
  (apply min (longest-chain limit)))

실행 결과는 다음과 같다. 답을 구하는 데 오래 걸린다.

p095> (time (solve))
"Elapsed time: 22100.70488 msecs"
14?16

심지어 위 시간은 맵을 구성하는 데 걸린 시간은 포함하지 않은 것이다. 여러 시도를 해봤지만 더 빠르게 문제를 푸는 방법을 찾지 못했다.

참고

프로젝트 오일러 95 풀이 소스 코드