[문제 출처 : Codechef] 이번에 풀어볼 문제는, 자연수들로 채워진 삼각형이 있을 때, 아래쪽 변까지 내려가면서 합을 냈을 때 최대의 합을 갖는 경로를 찾아 그 합을 출력하는 문제입니다.
제한 조건은 아래로 내려갈 때에 현재 숫자의 바로 아래와 오른쪽 아래, 이렇게 두 갈래 길로 갈 수 있다는 것입니다.
예를 들어, 삼각형이
1
2 1
1 2 3
로 되어 있을 때에, 최대 합은 경로를 1->2->2로 갈 때나, 1->1->3으로 갈 때에 5로 나오기 때문에 5를 출력하면 되는 것입니다.
어떤 방식으로 풀어야 가장 효과적으로 풀어낼 수 있을까요?
우리가 가장 먼저 생각해 볼 수 있는 방법은 모든 path를 고려하여 그 합들을 다 구해보고 비교해서 최대값을 찾아내는 방법입니다. Complexity를 생각해 보면, 각 점에서 2가지 경우(바로 아래, 오른쪽 아래)로 내려갈 수 있으므로, 결국 삼각형이 $R$개의 줄을 가지고 있을 때, \[O(2^{R-1})\approx O(2^R)\] 의 complexity를 갖는 것으로 생각할 수 있습니다. 하지만 complexity 중에서 가장 최악 중의 하나가 exponentially 증가하는 것인데, 정말로 $R$이 커질수록 매우 느려지게 됩니다.
이를 polynomial 함수로 바꿀 수 있다면 얼마나 좋을까요? ㅎㅎ 실제로 마법같이 $O(R^2)$로 획기적인 감소를 가지는 방법을 설명해 보겠습니다. 귀납적 추리와 비슷한 방법인데요, 먼저 $R-1$번째 줄에 있다고 가정해 봅시다. 그러면 마지막 $R$번째 줄을 갈 때에, 바로 아래와 오른쪽 아래의 두 수 중에 더 큰 값을 골라서 최종적인 경로를 완성할 것입니다. 결국 $R-1$번째 줄부터 가질 수 있는 최대 합은 \[MaxSum_{R-1,c} = n_{R-1,c} + \max(n_{R,c},n_{R,c+1})\] 이 됩니다.(여기서 c는 c번째 열을 말하는 것입니다.) 이런식으로 쭈욱 올라가면 결국 우리가 구하고자 하는 값은, \[MaxSum_{1,1} = n_{1,1} + \max(MaxSum_{2,1}, MaxSum_{2,2})\] 가 되겠지요. 이를 코드로 구현하면,
def findMaxSumPath(triangle):
for i in range(len(triangle)-2, -1, -1): #맨 끝줄부터 첫째줄까지 올라가면서,
for j in range(len(triangle[i])): #각 열마다
triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1])
return triangle[0][0]
>>> triangle = [[1], [2,1], [1,2,3]]
>>> findMaxSumPath(triangle)
5
>>> triangle = [[1], [1,2], [4,1,2], [2,3,1,1]]
>>> findMaxSumPath(triangle)
9맞는 답이 나옴을 확인할 수 있습니다. 이게 왜 $O(R^2)$의 complexity를 갖냐면, 각 숫자를 한번씩 방문하기 때문에, 첫 행에 1개, 두번째 행에 2개, …, R번째 행에 R개의 숫자가 있으므로, 결국 \[O(1+2+…+R)=O\left(\frac{R(R+1)}{2}\right)\approx O(R^2)\] 가 나오게 되고, 이는 엄청난 계산 성능의 개선으로 나타납니다 :) 즐거운 코딩 되셨길 :)