n_triangle
: 삼각형의 크기
triangle
: 삼각형
→ ex : [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
s_triangle
: 삼각형 각 자리에서의 최댓값. 삼각형 위부터 계산된다.
i 열 j행 최댓값 = max(i-1 열 j행 최댓값, i-1 열 j-1행 최댓값)
이용
import sys
from collections import deque
n_triangle = int(sys.stdin.readline())
triangle = [ list(map(int,list(sys.stdin.readline().strip().split()))) for _ in range(n_triangle)]
s_triangle = []
for i, nums in enumerate(triangle):
sums = []
if i == 0:
sums.append(triangle[0][0])
else:
for j,n in enumerate(nums):
if j == 0:
sums.append(n + s_triangle[i-1][0])
elif j == len(nums)-1:
sums.append(n + s_triangle[i-1][-1])
else:
sums.append(n+ max(s_triangle[i-1][j-1],s_triangle[i-1][j]))
s_triangle.append(sums)
print(max(s_triangle[-1]))