[백준] 1932번 파이썬

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

문제 해결 과정

1. 문제를 읽고, 예제를 보면 삼각형의 제일 위부터 값의 개수는 1개씩 증가한다. (1, 2, 3, 4 ,5 ...)

2. 아래층으로 내려갈 때, 위층에서 선택할 수 있는 아래층의 숫자는 오른쪽, 왼쪽 대각선에 있는 수만 가능하다.

3. 그림으로 보면 더 간단하다. 이렇게 누적 합을 구할 때, 아래층에서 수를 2개를 고를 수 있는 경우 합이 더 크게 만들어지는 숫자를 선택하면 된다.

import sys
input = sys.stdin.readline

n = int(input())
dp = []
for _ in range(n):
    dp.append(list(map(int, input().split())))
answer = dp[0][0]

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

print(answer)