정수 삼각형

• 1994년 IOI 문제. 프로그래머즈의 정수 삼각형도 동일한 문제이다. 풀이는 그쪽 참고.

"""Solution code for "BOJ 1932. 정수 삼각형".

- Problem link: https://www.acmicpc.net/problem/1932
- Solution link: http://www.teferi.net/ps/problems/boj/1932

Tags: [DP]
"""


def main():
    n = int(input())
    triangle = [[int(x) for x in input().split()] for _ in range(n)]

    dp_cur = [0] * (n + 1)
    for triangle_row in reversed(triangle):
        dp_prev = dp_cur
        dp_cur = [cur + max(sum_left, sum_right)
                  for cur, sum_left, sum_right
                  in zip(triangle_row, dp_prev, dp_prev[1:])]
    print(dp_cur[0])


if __name__ == '__main__':
    main()