[백준-파이썬] 1932: 정수 삼각형

문제 보러 가기!

하늘색 숫자는 원래 그 자리의 숫자이다.(arr에 저장했다.)
dp는 n X n 2차원 리스트로 만들었다. 세로는 위에서부터 몇 층 내려왔는지, 가로는 지금의 가로 위치를 뜻한다.
그 위치로 올 수 있는 숫자 중 큰 수(각 층에서 0번째 자리는 바로 위에서만 내려올 수만 있고, 가장 오른쪽 수는 대각선 왼쪽에서만 내려올 수 있다. 다른 수들은 바로 위 or 대각선 왼쪽 수 중 큰 수!! )에다가 원래 그 자리의 숫자를 더해서 저장했다.

아!
문제에 '아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.'라고 쓰여 있는데, 인덱스로 따지면..! 아래 그림처럼 된다.

노란 동그라미 친 숫자 기준으로 보면, 왼쪽 대각선 위에서 숫자가 내려 오거나, 오른쪽 대각선 위에서 숫자가 내려올 수 있다. 인덱스를 보면, 자기보다 하나 적은 것 or 같은 것이다..! 그래서 '바로 위(인덱스 같은 것) or 대각선 왼쪽 수(하나 적은 것)'라고 했다.

import sys

input = sys.stdin.readline
MIISS = lambda: map(int, input().strip().split())

n = int(input())
dp = [[0] * n for  _ in range(n)] # 세로: 위에서부터 몇 층 내려왔는지, 가로: 지금 위치

arr = tuple(tuple(MIISS()) for _ in range(n))

dp[0][0] = arr[0][0]

for i in range(1, n): # 층
    dp[i][0] = dp[i-1][0] + arr[i][0]

    for j in range(1, i): # 위치
        dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j]

    dp[i][i] = dp[i-1][i-1] + arr[i][i]

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