1001×1001 나선모양 행렬에서 대각선 원소의 합은?
대각선 원소에 대한 공식을 구하면 쉽게 문제를 풀 수 있다. 첫 번째 링의 요소는 다음과 같다.
여기서 대각선 요소를 작은 수부터 나열하면 3, 4, 7, 9다.
두 번째 링의 요소는 다음과 같다.
대각선 요소를 작은 수부터 나열하면 13, 17, 21, 25다. 세 번째 링도 그려볼 수 있지만 생략하겠다. 이 요소를 분석해 번째 링의 대각선 요소 수를 구하는 함수 의 공식을 유도하려 한다. 에는 0, 1, 2, 3이 들어갈 수 있다.
첫 번째 링의 대각선 요소 3, 5, 7, 9와 두 번째 링의 대각선 요소 13, 17, 21, 25를 자세히 살펴보면 규칙을 발견할 수 있다. 먼저 첫 번째 링의 대각선 요소부터 살펴보자. 첫 번째 링의 대각선 요소를 구하는 는 다음과 같이 쓸 수 있다.
두 번째 링의 대각선 요소를 구하는 는 다음과 같이 쓸 수 있다.
세 번째 링의 대각선 요소는 31, 37, 43, 49이며(연습장에 직접 그려서 확인해 보기 바란다), 는 다음과 같이 쓸 수 있다.
위 식을 보면 규칙이 보인다. 일때 각 항의 차는 2이고, 일때 각 항의 차는 4가 된며, 일때 각 항의 차는 6이 된다. 따라서 는 다음과 같이 쓸 수 있다.
여기서는 이 식이 옳은지 수학적으로 증명하지는 않을 것이다. 이 식이 맞는지는 문제의 답을 제대로 구하는지로 확인할 수 있다. 이제 코드를 작성할 차례다. 먼저 다음과 같이 size와 square 함수를 정의한다.
(def size 1001)
(defn- square [n] (* n n))
위에서 유도한 대각선 요소를 구하는 함수 d(n, k)는 다음과 같이 작성할 수 있다.
(defn- d [n k]
(+ (* 2 n (inc k)) (square (dec (* 2 n)))))
이제 을 증가시키며 대각선 요소를 구해 모두 더하면 된다. 행렬의 크기가 이므로 의 범위는 1부터 500까지가 될 것이다. 함수 는 링의 대각선 요소만 구하므로 행렬의 중앙에 있는 1은 직접 더해주어야 한다.
(defn solve []
(->> (for [n (range 1 (inc (int (/ size 2)))) k (range 4)] (d n k))
(apply +)
(+ 1)))
실행 결과는 다음과 같다.
p028=> (time (solve)) "Elapsed time: 11.123947 msecs" 6691710??
정답을 구하는 것으로 미루어 위에서 유도한 함수 의 식이 정확함을 알 수 있다.