프로젝트 오일러 28

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

프로젝트 오일러 28

1001×1001 나선모양 행렬에서 대각선 원소의 합은?

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

대각선 원소에 대한 공식을 구하면 쉽게 문제를 풀 수 있다. 첫 번째 링의 요소는 다음과 같다.

%math \begin{matrix} 7 & 8 & 9 \newline 6 & & 2 \newline 5 & 4 & 3 \end{matrix}

여기서 대각선 요소를 작은 수부터 나열하면 3, 4, 7, 9다.

두 번째 링의 요소는 다음과 같다.

%math \begin{matrix} 21 & 22 & 23 & 24 & 25 \newline 20 & & & & 10 \newline 19 & & & & 11 \newline 18 & & & & 12 \newline 17 & 16 & 15 & 14 & 13 \end{matrix}

대각선 요소를 작은 수부터 나열하면 13, 17, 21, 25다. 세 번째 링도 그려볼 수 있지만 생략하겠다. 이 요소를 분석해 n 번째 링의 대각선 요소 수를 구하는 함수 d(n, k) 의 공식을 유도하려 한다. k 에는 0, 1, 2, 3이 들어갈 수 있다.

첫 번째 링의 대각선 요소 3, 5, 7, 9와 두 번째 링의 대각선 요소 13, 17, 21, 25를 자세히 살펴보면 규칙을 발견할 수 있다. 먼저 첫 번째 링의 대각선 요소부터 살펴보자. 첫 번째 링의 대각선 요소를 구하는 d(1, k) 는 다음과 같이 쓸 수 있다.

%math \begin{aligned} d(1, k) &= 2k + 3 \newline &= 2(k+1) + 1^2 \end{aligned}

두 번째 링의 대각선 요소를 구하는 d(2, k) 는 다음과 같이 쓸 수 있다.

%math \begin{aligned} d(2, k) &= 4k + 13 \newline &= 4(k+1) + 9 \newline &= 2 \cdot 2(k+1) + 3^2 \end{aligned}

세 번째 링의 대각선 요소는 31, 37, 43, 49이며(연습장에 직접 그려서 확인해 보기 바란다), d(3, k) 는 다음과 같이 쓸 수 있다.

%math \begin{aligned} d(3, k) &= 6k + 31 \newline &= 6(k+1) + 25 \newline &= 2 \cdot 3(k+1) + 5^2 \end{aligned}

위 식을 보면 규칙이 보인다. n=1 일때 각 항의 차는 2이고, n=2 일때 각 항의 차는 4가 된며, n=3 일때 각 항의 차는 6이 된다. 따라서 d(n, k) 는 다음과 같이 쓸 수 있다.

%math \begin{aligned} d(n,k) &= 2n(k+1) + (2n-1)^2 \newline n &= 1, 2, 3, ... \newline k &= 0, 1, 2, 3 \end{aligned}

여기서는 이 식이 옳은지 수학적으로 증명하지는 않을 것이다. 이 식이 맞는지는 문제의 답을 제대로 구하는지로 확인할 수 있다. 이제 코드를 작성할 차례다. 먼저 다음과 같이 sizesquare 함수를 정의한다.

(def size 1001)
(defn- square [n] (* n n))

위에서 유도한 대각선 요소를 구하는 함수 d(n, k)는 다음과 같이 작성할 수 있다.

(defn- d [n k]
  (+ (* 2 n (inc k)) (square (dec (* 2 n)))))

이제 n 을 증가시키며 대각선 요소를 구해 모두 더하면 된다. 행렬의 크기가 1001\times1001 이므로 n 의 범위는 1부터 500까지가 될 것이다. 함수 d(n, k) 는 링의 대각선 요소만 구하므로 행렬의 중앙에 있는 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??

정답을 구하는 것으로 미루어 위에서 유도한 함수 d(n,k) 의 식이 정확함을 알 수 있다.

참고