백준 1932. 정수 삼각형

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

1932번: 정수 삼각형

'''
한 층에 하나씩(현재 위치에서 대각선 이동)누적합
최대 합 구하기!
'''

import sys
input = sys.stdin.readline

n = int(input()) # 삼각형의 크기(몇 층까지 있음?)
arr = [list(map(int,input().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)] # 각각의 층에 도착했을 때의 최댓값
dp[0][0] = arr[0][0] # 0층 초기화
for i in range(1,n): # i는 1층~n-1층 모든 층 순회
    for j in range(i+1): # j는 각 층의 모든 수 순회
        if j == 0: # 첫번째 수
            dp[i][j] = dp[i-1][j] + arr[i][j]
        elif j == i: # 마지막 수
            dp[i][j] = dp[i-1][j-1] + arr[i][j]
        else: # 중간 수(비교 후 갱신 필요)
            dp[i][j] = max(dp[i-1][j-1] + arr[i][j], dp[i-1][j] + arr[i][j])
print(max(dp[n-1]))