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

풀이

삼각형을 2차원 배열로 입력받은 뒤, 2번째 행부터 그 전 행의 숫자를 축적하며 더한다.
수의 합이 최대가 되어야하므로, 대각선 왼쪽 또는 오른쪽에 있는 수 중에 최댓값만 더하면 된다.
다만 첫번째 열과 마지막 열은 대각선에 있는 수가 하나밖에 없으므로 예외처리를 해준다.
모두 계산했으면 배열의 마지막 행에서 최댓값을 출력해준다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
tri = []

for _ in range(n):
    tri.append(list(map(int, input().strip().split())))

for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            tri[i][0] += tri[i-1][0]
        elif j == i:
            tri[i][j] += tri[i-1][j-1]
        else:
            tri[i][j] += max(tri[i-1][j], tri[i-1][j-1])

print(max(tri[n-1]))