프로젝트 오일러 149번

Looking at the table below, it is easy to verify that the maximum possible sum of adjacent numbers in any direction (horizontal, vertical, diagonal or anti-diagonal) is \(16\; (=8+7+1)\).

−2	5	3	2
9	−6	5	1
3	2	7	3
−1	8	−4	8

Now, let us repeat the search, but on a much larger scale:

First, generate four million pseudo-random numbers using a specific form of what is known as a "Lagged Fibonacci Generator":

For \(1 \le k \le 55\), \(s_k = \left [100003-200003k+300007k^3 \right ]\; ({\rm modulo}\;1000000)-500000\).

For \(56 \le k \le 4000000\), \(s_k = \left [ s_{k-24} + s_{k-55} + 1000000 \right ] \; ({\rm modulo} \; 1000000)-500000\).

Thus, \(s_{10}=-393027\) and \( s_{100}=86613\).

The terms of \(s\) are then arranged in a \(2000 \times 2000\) table, using the first \(2000\) numbers to fill the first row (sequentially), the next \(2000\) numbers to fill the second row, and so on.

Finally, find the greatest sum of (any number of) adjacent entries in any direction (horizontal, vertical, diagonal or anti-diagonal).

---

위의 표를 보면 행이나 열, 혹은 대각선 방향으로 나열된 수들 중 이웃한 수들의 합의 최댓값은 \(16\; (=8+7+1)\) 이 된다는 것을 쉽게 알아낼 수 있다.  (예를 들어, 1행에서 이웃한 수들의 합의 최댓값은 \(10\), 2행에서 이웃한 수들의 합의 최댓값은 \(9\), 1열에서 이웃한 수들의 합의 최댓값은 \(12\) 가 된다.)

이제 좀 더 큰 사이즈의 표를 생각해 보도록 하자.

먼저 다음과 같은 규칙에 따라 항의 개수가 사백만(\(4000000\)) 개인 수열 \(\{s_k\}\) 를 만들어 보자.

\(1 \le k \le 55\) 일 때,  \(s_k = \left [100003-200003k+300007k^3 \right ]\; ({\rm modulo}\;1000000)-500000\).

\(56 \le k \le 4000000\) 일 때, \(s_k = \left [ s_{k-24} + s_{k-55} + 1000000 \right ] \; ({\rm modulo} \; 1000000)-500000\).

(단, \([a]\; ({\rm modulo}\;B)\) 는 \(A\) 를 \(B\) 로 나눈 나머지를 나타낸다.)

이렇게 만든 수열에서 \(s_{10}=-393027\), \(s_{100}=86613\) 이 될 것이다.

이제 이 수열의 일반항들을 \(2000 \times 2000\) 크기의 표에 채워 넣어야 한다. 처음 \(2000\) 개의 항은 제\(1\)행에, 다음 \(2000\) 개의 항은 제 \(2\)행에 채워 넣는 형식으로 표를 채워 간다.

이렇게 만들어진 \(2000 \times 2000\) 크기의 표에서 행, 열, 대각선 방향의 이웃한 수들의 합의 최댓값은 얼마일까?

이 문제를 풀기 위해서는 Kadane's algorithm 을 알고 있어야 한다. Kadane's algorithm 은 크기가 \(n\) 으로 주어진 배열 \(a\) 에 대하여 이웃한 수들의 합의 최댓값을 구하는 알고리즘으로 다음과 같은 과정을 따른다. 

먼저 \(Q[i]\) 를 배열 \(a\) 의 \(i\) 번째 요소까지의 이웃한 수들의 합의 최댓값이라고 하자.

1. \(Q[0] = a[0]\)

2. \(1 \le i \le n\) 에 대하여 \[Q[i] = {\rm max}(Q[i-1] + a[i], \; a[i])\] 를 계산한 후, \[{\rm maximum} = {\rm max} ( {\rm maximum},\; Q[i] ) \] 로 \(\rm maximum\) 을 업데이트 한다. (단, \({\rm max}(a, \;b)\) 는 \(a, \;b\) 중 작지 않은 값을 나타낸다.) 

3. 루프가 끝난 후의 \(\rm maximum\)이 우리가 찾는 이웃한 수들의 합이 최댓값이 된다.

위와 같은 방법을 표의 모든 행에 적용하여 각 행의 최댓값을 찾은 후, 다시 행들간 최댓값을 찾아낸다. 이 과정을 열에 대해서 또 두 방향의 대각선에 대해서 모두 적용하여 그 중 가장 최대인 값을 찾아낸다. 

대각선 방향의 수들을 배열로 만드는 방법은 각자 해결할 수 있으리라 믿는다.