프로젝트 오일러 150번

In a triangular array of positive and negative integers, we wish to find a sub-triangle such that the sum of the numbers it contains is the smallest possible.

In the example below, it can be easily verified that the marked triangle satisfies this condition having a sum \(-42\).

We wish to make such a triangular array with one thousand rows, so we generate \(500500\) pseudo-random numbers \(s_k\) in the range \(\pm 2^{19}\), using a type of random number generator (known as a Linear Congruential Generator) as follows:

   \(t = 0\)

   for \(k=1\) up to \(k=500500\)

      \(t= (615949 \times t + 797807) \; {\rm modulo}\;  2^{20}\)

      \(s_k = t-2^{19}\)

Thus \(s_1=273519, \;s_2=-153582,\;s_3=450905\) etc

Our triangular array is then formed using the pseudo-random numbers thus:

s₁
s₂ s₃
s₄ s₅ s₆
s₇ s₈ s₉ s₁₀
...

Sub-triangles can start at any element of the array and extend down as far as we like (taking-in the two elements directly below it from the next row, the three elements directly below from the row after that, and so on).

The "sum of a sub-triangle" is defined as the sum of all the elements it contains.

Find the smallest possible sub-triangle sum.

---

양의 정수와 음의 정수로 이루어진 삼각형 모양의 배열이 있다고 하자. 이 배열의 전부 혹은 일부분으로 만들 수 있는 삼각형 안에 속하는 모드 수들의 합이 최소가 되는 경우를 찾는 것이 이번 문제에서 해야 할 일이다. 

아래의 예제에서 보이는 삼각형 모양의 배열에서는 빨간색 삼각형 안에 속하는 수들의 합이 \(-42\) 로 최소가 된다는 것을 알 수 있다. 

자 이제 문제에서 사용할 삼각형 모양의 배열을 만들기 위해서 항의 개수가 \(500500\) 개인 수열 \(\{S_k\}\) 를 먼저 생각하자. \(s_k\) 의 모든 항들은 \(\left (-2^{19}, \; 2^{19} \right )\) 범위에 있으며 다음의 규칙에 따라 만들어진다.

   \(t = 0\)

   for \(k=1\) up to \(k=500500\)

      \(t= (615949 \times t + 797807) \; {\rm modulo}\;  2^{20}\)

      \(s_k = t-2^{19}\)

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

위 규칙대로라면 \(s_1=273519, \;s_2=-153582,\;s_3=450905,\; \cdots \) 가 될 것이다. 

이제 이 수열을 이용해서 삼각형을 만들면 다음과 같은 형태가 될 것이다.

s₁
s₂ s₃
s₄ s₅ s₆
s₇ s₈ s₉ s₁₀
...

위 삼각형의 일부분으로 만들 수 있는 삼각형의 가장 위 꼭짓점이 되는 수는 \(500500\) 개의 \(s_k\) 가 모두 가능하고, 아래로 내려갈 수록 수의 개수가 하나 씩 증가하는 이등변삼각형의 모양을 하게 될 것이다. 따라서 부분 삼각형의 총합이란 이렇게 만든 삼각형 내에 포함되는 모든 수들의 합을 뜻한다.

그렇다면 이 문제에서 부분 삼각형의 총합이 최소가 될 때, 그 최솟값은 얼마이겠는가?

이 문제를 여러 모로 생각해 봐도 답을 찾을 수 있는 방법은 모든 부분 삼각형의 총합을 구하여 그 중 최솟값을 구하는 것이다. (물론 내 머리가 더 이상 원활하게 돌지 않고 있기는 하지만...ㅠㅠ)

먼저 문제에서 주어진 규칙대로 각 행을 모두 배열로 만들고, 그 배열들을 요소로 하는 또 다른 배열을 만든다. (파이썬에서는 리스트를 사용하면 편한다.) 이렇게 만든 배열은 크기가 \(1000\) 이 될 것이고, 이 배열의 \(n\) 번째 성분은 크기가 \(n\) 인 배열이 되는 것이다. 

다음에는 각 행별로 누적합을 요소로 갖는 새로운 배열을 만든다.

예를 들어, \(3\) 행이 \([1, \;2,\; 3]\) 이었다면 누적합을 요소로 갖는 배열은 \([1, \;3, \; 6]\) 이 될 것이다. 이 누적합을 이용하여 부분으로 만든 삼각형의 각 행의 총합을 쉽게 구할 수 있다. 다음의 파이썬 코드를 보자.

accsumtri = []
for i in triangle:
	cursum = 0
	temp = [0]
	for j in i:
		cursum += j
		temp.append(cursum)
	accsumtri.append(temp)


minimum = 10 ** 9
for i in range(1000):
	for j in range(i + 1):
		cursum = 0
		for k in range(i, 1000):
			cursum += accsumtri[k][j + 1 + k - i] - accsumtri[k][j]
			minimum = min(minimum, cursum)

위에서 triangle 은 규칙대로 만든 배열이고, accsumtri 는 누적합으로 만든 배열이다. 여기서 특이한 것은 accsumtri 에서 각 행에 해당하는 배열은 항상 \(0\) 으로 시작한다. 이는 각 행의 첫 번째 성분이 삼각형의 맨 위 꼭짓점이 되는 경우 합을 구하기 편하게 하기 위함이다. 예를 들어, asscumtri가 다음과 같이 이루어졌다고 해 보자.

\(0\; 1\)

\(0\; 2\; 5\)

\(0\; 3\; 7\; 8\)

\(0 \;1 \;5 \;8 \;9\)

이때 \(2\) 행의 \(2\)를 꼭짓점으로 하는 부분 삼각형을 생각한다면 다음과 같이 계산이 된다.

\((2-0)\)

\((2-0) + (7-0)\)

\((2-0)+(7-0)+(8-0)\)

만약 \(2\) 행의 \(5\) 를 꼭짓점으로 하는 부분 삼각형을 만들어 간다면

\((5-2)\)

\((5-2)+(8-3)\)

\((5-2)+(8-3)+(9-1)\)

과 같이 계산이 될 것이다. 

이런식으로 계산을 해서 최솟값을 찾아 나가는 방식이다. 코드를 보면 이해가 갈 것이다. 그림을 그려 가면서 코드를 살펴보면 이해하기 쉬울듯...

이렇게 하면 답이 나오기 까지 몇 분이 걸리지 않는다. C로 코딩을 하면 좀 더 빠르게 답을 구할 수 있다고는 하는데, 이 문제는 그냥 이 선에서 마무리 할까 한다.