프로젝트 오일러 100

내 이 세상 도처에서 쉴 곳을 찾아보았으나, 마침내 찾아낸, 컴퓨터가 있는 구석방보다 나은 곳은 없더라.

on Project-Euler Clojure

프로젝트 오일러 100

두 개의 파란 공이 뽑힐 확률이 50%인 경우

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

공 전체 개수를 n , 파란 공 개수를 b 라 하면, 상자에서 무작위로 두 개의 공을 꺼냈을 때 두 개가 모두 파란 색일 확률은 다음과 같이 나타낼 수 있다.

%math \begin{aligned} P = \frac{b}{n} \cdot \frac{b-1}{n-1} = \frac{1}{2} \end{aligned}

이 식을 정리하면 다음 방정식을 얻을 수 있다.

%math \begin{aligned} 2b^2 - 2b - n^2 + n = 0 \end{aligned}

이 방정식에서 n 이 10^{12} 이상인 정수해 중 가장 작은 b 값을 찾으면 문제를 풀 수 있지만, 이 방정식을 직접 풀기는 어려울 것 같다. 구글에서 'two integer variable equation'으로 검색해보니 Generic two integer variable equation solver란 아주 훌륭한 사이트를 찾을 수 있었다. a⁢x^2 + b⁢x⁢y + c⁢y^2 + d⁢x + e⁢y + f = 0 형태의 두 변수를 가지는 방정식에서 계수 a, b, c, d, e, f 를 입력하면 방정식의 해를 구해주는 사이트다. 여기서는 a=2 , b=0 , c=-1 , d=-2 , e=1 , f=0 을 입력하면 다음과 같이 재귀적 해를 구할 수 있는 공식을 얻을 수 있다.

%math \begin{aligned} b_{k+1} = 3b_k + 2n_k - 2 \newline n_{k+1} = 4b_k + 3n_k - 3 \end{aligned}

이 식은 Clojure 함수로 다음과 같이 나타낼 수 있다.

(defn next-b [b n] (+ (* 3 b) (* 2 n) -2))
(defn next-n [b n] (+ (* 4 b) (* 3 n) -3))

문제는 다음과 같이 풀 수 있다. 계속 다음 해를 구해가다 n 이 10^{12} 를 넘을 때 b 값이 답이 된다.

(def target 1000000000000)

(defn solve []
  (loop [b 15, n 21]
    (if (< n target)
      (recur (next-b b n) (next-n b n))
      b)))

실행 결과는 다음과 같다. 빠르게 답을 구한다.

p100=> (time (solve))
"Elapsed time: 0.055501 msecs"
75687232??73

참고