[백준_1932] 정수 삼각형 python

원리만 파악하면다면 매우 쉽게 해결할 수 있는 문제였다.

# n입력

n = int(input())

# tri 설계

tri = []

# tri 입력

for _ in range(n):

　tri.append(list(map(int, input().split())))

# dp 설계

dp = [

　[0] * n for _ in range(n)

]

# dp 초기설정

dp[0][0] = tri[0][0]

j = 1

for i in range(1, n):

　dp[i][0] = tri[i][0] + dp[i-1][0]

　dp[i][j] = tri[i][j] + dp[i-1][j-1]

　j += 1

# dp 채워넣기

for i in range(2, n):

　for j in range(1, i):

　　dp[i][j] = tri[i][j] + max(dp[i-1][j-1], dp[i-1][j])

# 출력

print(max(dp[-1]))