#147 백준 파이썬 [1932] 정수 삼각형

https://www.acmicpc.net/problem/1932

 

#Solution

삼각형의 제일 밑에서부터 최댓값을 저장해가면서 올라간다. 대각선 왼쪽 아래와 대각선 오른쪽 아래 중 큰 수와 자기자신을 더한 값이 그 아래 경로의 최댓값이다.

triangle = int(input())
triangle_matrix = []
max_matrix = [[] for _ in range(triangle)]

for _ in range(triangle):
    triangle_matrix.append(list(map(int, input().split())))

#역순으로 하위 항목을 모두 더한 최댓값을 저장
for i in range(triangle - 1, -1, -1):
    for j in range(len(triangle_matrix[i])):
        if i == triangle - 1:
            max_matrix[i].append(triangle_matrix[i][j])
        else:
            max_matrix[i].append(triangle_matrix[i][j] + max(max_matrix[i+1][j], max_matrix[i+1][j+1]))

print(max_matrix[0][0])