파이썬) 백준 알고리즘 | 1932번 : 정수 삼각형

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

1932번: 정수 삼각형

 

풀이

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

이 경우에서는

7

10 15

18 16 15

20 25 20 19

24 30 27 26 24

이런식으로 각 줄마다 합이 최대가 되는 경로의 수를 만들면 됩니다.

 

n = int(input())
nums = []
for i in range(n):
    a = list(map(int, input().split()))
    a.extend([0] * (500- len(a)))
    nums.append(a)
for i in range(1, n):
    for j in range(i+1):
        nums[i][j] = max(nums[i-1][j-1], nums[i-1][j]) + nums[i][j]
print(max(nums[n-1]))