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

일때 의 값이 1백만을 넘는 경우는 모두 몇 번?
문제 자세히 보기: [국어] [영어]

이므로 , 의 범위는 각각 , 이다. 모든 , 조합에 대해 을 구한다 해도 경우의 수는 이므로 금방 구할 수 있다.

방법 1

factorial 함수를 이용하면 을 구하는 함수는 다음과 같이 간단히 작성할 수 있다.

(ns p053
  (:require [util :refer [factorial]]))

(defn c [n r]
  (/ (factorial n) (*' (factorial r) (factorial (- n r)))))

이제 과 을 부터 까지 바꿔가며 값을 구한 다음 이상의 값만 필터링해 개수를 세면 된다.

(defn solve []
  (->> (for [n (range 1 101) r (range 1 101)] (c n r))
       (filter #(>= % 1000000))
       count))

실행 결과는 다음과 같다.

p053=> (time (solve))
"Elapsed time: 485.574244 msecs"
40??

이렇게 풀고 나니 문제가 너무 쉽다. 사실 이 문제의 의도는 큰 수를 계산하는 방법에 관한 것일 듯 하다. 팩토리얼은 매우 빠르게 증가하기 때문에 정도만 돼도 Long/MAX_VALUE를 가볍게 넘는다. 따라서 Clojure의 BigInt와 *' 함수가 아니었다면 답을 구하기가 쉽지 않았을 것이다.

방법 2

을 구할 때 팩토리얼을 먼저 계산하지 않고 나눗셈을 먼저 계산하면 계산 과정에서 숫자가 지나치게 커지는 문제를 피할 수 있다.

수식을 잘 보면 알겠지만 분모와 분자의 항 수가 항상 같다. 그리고 C/C++ 또는 Java의 / 연산자는 결과가 항상 정수인 것과 달리 Clojure의 / 함수는 분수(clojure.lang.Ratio)를 리턴할 수 있다. 이 두 가지를 이용하면 다음과 같이 나눗셈을 먼저 계산하로록 함수를 작성할 수 있다.

(defn c [n r]
  (let [nu (range 1 (inc n))
        de (concat (range 1 (inc r)) (range 1 (inc (- n r))))]
    (->> (map / nu de)
         (reduce *))))

factorial을 사용하지 않고도 비교적 간단하게 을 계산할 수 있게 되었다. 계산하면서 중간 결과가 BigInt로 확장되지 않아서 그런지 실행 속도도 빨라졌다.

p053=> (time (solve))
"Elapsed time: 161.206506 msecs"
40??

수식을 자세히 살펴보면 뒷부분은 1로 약분되기 때문에 굳이 계산하지 않아도 된다.

따라서 함수를 다음과 같이 수정할 수 있다.

(defn c [n r]
  (let [nu (range (inc (- n r)) (inc n))
        de (range 1 (inc r))]
    (->> (map / nu de)
         (reduce *))))

참고

프로젝트 오일러 53 풀이 소스 코드
프로젝트 오일러 15 팩토리얼 함수를 구현하는 방법에 대해 설명했다.