Q32. 정수 삼각형

1932번: 정수 삼각형 (acmicpc.net)

1932번: 정수 삼각형

 

삼각형을 위에서 아래로 쫙 훑으면서 각 숫자가 아래층 대각선 숫자에 더해졌을 때의 최대값을 계속 갱신해주면된다.

 

n = int(input())

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

for i in range(n-1):
    for j in range(len(tri[i])):
        dp[i+1][j] = max(dp[i+1][j], tri[i+1][j] + dp[i][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], tri[i+1][j+1] + dp[i][j])

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