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

 
 
# 정수 삼각형
 
# 누적으로 풀었다. 풀어본 유형이여서 쉽게 풀 수 있었다.
 
n = int(input())
 
k = [ ]
 
for i in range(n):
    k.append(list(map(int,input().split(" "))))
 
 
 
if n==1:
    print(k[0][0])
 
elif n==2:
    print(max(k[1][1]+k[0][0],k[1][0]+k[0][0]))
 
else:
 
    k[1][1] += k[0][0]
    k[1][0] += k[0][0]
 
 
    for i in range(2,n):
 
        for j in range(0,len(k[i])):
 
            if j==0:
                k[i][0] += k[i-1][0]
 
 
 
            elif j==len(k[i])-1:
                k[i][j] += k[i-1][j-1]
 
            else:
                k[i][j] += max(k[i-1][j],k[i-1][j-1])
 
 
    print(max(k[-1]))