[DP]1932号-整数三角形(30日目)

# 코드 실행속도 단축
import sys
input = sys.stdin.readline
# 정수 삼각형 길이 입력
n = int(input())
# 정수 삼각형 2차원 list로 저장
trigle = [list(map(int, input().split())) for _ in range(n)]
# 각 줄의 번호(1~n)에 해당하는 크기로 2차원 DP list 생성
dp = [[0 for _ in range(i)] for i in range(1,n+1)]
# 첫번째 DP의 값 정수 삼각형의 root 값으로 저장
dp[0][0] = trigle[0][0]

# 0~n-1줄까지 반복
for i in range(n-1):
    # 해당 줄의 길이 만큼 반복
    for j in range(len(trigle[i])):
        # 해당 줄의 인덱스의 dp값 + 좌측 대각선 아래 정수값과 좌측 대각선 아래 dp값 중 큰 값을 dp에 저장
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + trigle[i+1][j])
        # 해당 줄의 인덱스의 dp값 + 우측 대각선 아래 정수값과 우측 대각선 아래 dp값 중 큰 값을 dp에 저장
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + trigle[i+1][j+1])
        
# DP 가장 마지막 줄의 최대값 출력
print(max(dp[-1]))