1932번 - 정수 삼각형(Python)

풀이

바닥 칸에서부터 특정 칸까지의 경로의 합 중 최댓값을 저장한다.

n-1번째 줄부터 자신의 아래층의 두 값중 최댓값과 자신의 값을 더해 저장한다.

코드

n = int(input())
triangle = [list(map(int, input().split())) for _ in range(n)]

for i in range(n-2, -1, -1):
    for j in range(i+1):
        triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1])

print(triangle[0][0])