프로젝트 오일러 94

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

on Project-Euler Clojure

프로젝트 오일러 94

정수 둘레와 정수 넓이를 갖는 거의 정삼각형 찾기

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

다음 그림과 같이 빗변을 a , 밑변을 b 라 하면, b = a \pm 1 인 경우가 문제에서 말하는 거의 정삼각형이라 할 수 있다. 삼각형의 높이를 h 라 하면 피타고라스 정리에 의해 다음 관계가 성립한다.

%math a^2 = \left( \frac{b}{2} \right)^2 + h^2

triangle

여기에 b = a \pm 1 을 대입해 정리하면 다음 식을 얻을 수 있다.

%math \begin{aligned} a^2 = \left( \frac{a \pm 1}{2} \right)^2 + h^2 \newline a^2 = \frac{a^2 \pm 2a + 1}{4} + h^2 \newline 3a^2 \pm 2a - 4h^2 = 1 \end{aligned}

양변에 3을 곱한 다음 (3a \pm 1) 의 제곱 형태로 수식을 변형할 수 있다.

%math \begin{aligned} 9a^2 \pm 6a - 12h^2 = 3 \newline (9a^2 \pm 6a + 1) - 12h^2 = 4 \newline (3a \pm 1)^2 - 12h^2 = 4 \end{aligned}

다시 양변을 4로 나누어 정리하면 다음 식을 얻을 수 있다.

%math \left( \frac{3a \pm 1}{2} \right) ^ 2 - 3h^2 = 1

여기서 \frac{3a \pm 1}{2} = x 로, h = y 로 치환하면 다음 식을 얻는다. 문제 66에서 다루었던 펠 방정식이 된다.

%math x^2 - 3y^2 = 1

펠 방정식 x^2 - ny^2 = 1 의 해를 구하는 방법은 위키피디아에 나와있다.

%math \begin{aligned} x_{k+1} &= x_1 x_k + ny_1 y_k \newline y_{k+1} &= x_1 y_k + y_1 x_k \end{aligned}

여기서 n 은 3이고, 첫 해 (x_1, y_1)=(2,1) 이다. 따라서 x_k, y_k 가 주어졌을 때 x_{k+1}, y_{k+1} 을 구하는 함수는 다음과 같이 작성할 수 있다.

(defn next-pair [[x y]]
  [(+' (*' 2 x) (*' 3 1 y))             ;next-x
   (+' (*' 2 y) (*' 1 x))])             ;next-y

주어진 x 에 대해 삼각형의 둘레길이와 넓이를 구하는 함수는 다음과 같이 작성할 수 있다. b = a + 1 인 경우와 b = a - 1 인 경우를 쌍으로 구한다.

(defn perimeter [x]
  [(+ (* 2 x) 2)                        ;for case 1 (a, a, a+1)
   (- (* 2 x) 2)])                      ;for case 2 (a, a, a-1)

(defn area [[x y]]
  [(* (/ (+ x 2) 3) y)                  ;for case 1 (a, a, a+1)
   (* (/ (- x 2) 3) y)])                ;for case 2 (a, a, a-1)

변의 길이는 a, b 로 나타내야 하므로 x 를 a 로 변환하는 함수가 필요하다. b = a \pm 1 이므로 a 를 알면 b 는 쉽게 구할 수 있다.

(defn x-to-a [x]
  [(/ (+ (* 2 x) 1) 3)                  ;for case 1 (a, a, a+1)
   (/ (- (* 2 x) 1) 3)])                ;for case 2 (a, a, a-1)

(x, y) 가 주어지면 변의 길이, 넓이, 둘레길이를 한꺼번에 구하는 함수는 다음과 같이 작성할 수 있다.

(defn side-area-perimeter [[x y]]
  (let [[s1 s2] (x-to-a x)
        [a1 a2] (area [x y])
        [p1 p2] (perimeter x)]
    [{:side s1 :area a1, :perimeter p1}
     {:side s2 :area a2, :perimeter p2}]))

이제 문제를 다음과 같이 풀 수 있다. 변의 길이, 넓이, 둘레길이를 구해 둘레길이가 10억보다 작거나 같으면서 변의 길이가 정수인 경우, 넓이가 정수인 경우만 걸러낸 다음 둘레길이를 모두 더하면 된다.

(def limit 1000000000)

(defn solve []
  (->> (iterate next-pair [2 1])
       (mapcat side-area-perimeter)
       (filter (fn [{s :side}] (integer? s)))
       (filter (fn [{a :area}] (and (< 0 a) (integer? a))))
       (take-while (fn [{p :perimeter}] (<= p limit)))
       (map (fn [{p :perimeter}] p))
       (apply +)))

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

p094=> (time (solve))
"Elapsed time: 0.92142 msecs"
5184??346

참고