직각삼각형을 만들어내는 방법이 한 가지 뿐인 경우 세기
합이 이하인 피타고라스 수(Pythagorean Triplet)의 시퀀스를 생성한 다음, 합으로 group-by 해서 값(피타고라스 수 목록)의 길이가 인 키의 개수를 세면 된다. 피타고라스 수를 구하는 방법은 문제 39에서 설명했다.
를 무한대까지 조사할 수는 없으므로 적절한 범위를 구해야 한다. 문제와 피타고라스 수 공식을 잘 살펴보면 다음과 같은 사실을 정리할 수 있다. 편의상 철사 길이 최대값을 로, 의 최대값을 으로 표시한다.
- 는 모두 양의 정수다. 이므로, 다.
- 이 최대가 되려면 가 최소가 되어야 한다. 의 최소값은 모두 이다.
- 이므로, 에 위 식을 대입하고 에 최소값()을 대입해 정리하면 다음 식을 얻을 수 있다.
이 충분히 크면 로 볼 수 있다. 따라서 의 최대값은 라 할 수 있다.
따라서 다음과 같이 상수를 정의하고,
(ns p075
(:require [util :refer [gcd]]))
(def L 1500000) ; max length of wire
(def M (int (Math/sqrt (quot L 2)))) ; max of m
처음 설명한 로직을 그대로 코드로 옮기면 답을 구할 수 있다.
(defn solve1 []
(->> (for [m (range 2 (inc M))
n (range 1 m)
k (range)
:let [a (* k (- (* m m) (* n n)))
b (* k 2 m n)
c (* k (+ (* m m) (* n n)))
sum (+ a b c)]
:while (<= sum L)
:when (odd? (- m n))
:when (= 1 (gcd m n))]
[a b c])
(group-by (fn [[a b c]] (+ a b c)))
(filter (fn [[_ ls]] (= 1 (count ls))))
count))
한 가지 중요한 점은, for안에서 :while이 :when보다 먼저 나와야 한다는 것이다. 순서가 바뀌면 의도한 결과가 나오지 않는다. 이 코드의 경우는 무한 루프에 빠지는 것 같다.
실행 결과는 다음과 같다. 속도가 만족스럽지는 않다.
p075=> (time (solve1)) "Elapsed time: 2473.175672 msecs" 161667
가만히 생각해보니, [a b c]를 구한 후 어차피 (+ a b c)를 계산하는 데만 사용할 뿐 a, b, c 값을 따로 사용할 일은 없다. 불필요하게 [a b c] 벡터를 구할 필요 없이 sum으로 시퀀스를 만들면 성능이 조금 나아지지 않을까?
(defn solve2 []
(->> (for [m (range 2 (inc M))
n (range 1 m)
k (range)
:let [a (* k (- (* m m) (* n n)))
b (* k 2 m n)
c (* k (+ (* m m) (* n n)))
sum (+ a b c)]
:while (<= sum L)
:when (odd? (- m n))
:when (= 1 (gcd m n))]
sum)
(group-by identity)
(filter (fn [[_ ls]] (= 1 (count ls))))
count))
개선한 코드의 실행 결과는 다음과 같다.
p075=> (time (solve2)) "Elapsed time: 2448.249765 msecs" 16??67
많이 빨라질 줄 알았는데, 거의 차이가 없다. 실행 순서(solve1을 먼저 실행하고 solve2를 실행했는지, 그 반대로 했는지)에 따라 결과가 뒤집히기도 하므로 사실상 차이가 없다고 봐도 무방할 것이다.