프로젝트 오일러 25

피보나치 수열에서 처음으로 1000자리가 되는 항은 몇 번째?

문제 자세히 보기: [국어] [영어]

피보나치 수열을 구하는 방법은 프로젝트 오일러 2번 풀이에서 설명했다. 2번에서는 4백만 이하의 항을 다루었지만 이 문제에서는 1,000자리가 되는 항을 구해야 하므로 피보나치 수열을 계산할 때 + 대신 자릿수에 관계 없이 계산할 수 있는 +'를 사용해야 한다.

(def fibo-iter
  (->> (iterate (fn [[a b]] [b (+' a b)]) [1 1])
       (map first)))

처음으로 1,000자리라 되는 항이 몇 번째인지를 구해야 하므로 map-indexed를 사용했다. 자릿수는 여러 가지 방법으로 구할 수 있지만, 여기서는 숫자를 문자열로 변환해 길이를 구하는 방식을 사용했다.

(defn solve []
  (->> fibo-iter
       (map-indexed (fn [i e] [(inc i) e]))
       (drop-while (fn [[_ a]] (< (count (str a)) 1000)))
       ffirst))

실행 결과는 다음과 같다.

p025=> (time (solve))
"Elapsed time: 146.081263 msecs"
47??

참고

• 프로젝트 오일러 25 풀이 소스 코드
• 프로젝트 오일러 2
• 정수 자릿수 구하기