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

파이썬 문법이 익숙하지 않아서 애먹었다.

 

우선 어떻게 해결할지 고민했는데 처음엔 제일 위에서 부터 큰 숫자를 찾으려 했으나 왼쪽 혹은 오른쪽 대각선만 선택할수 있어서 다른 방법을 찾아야했다.

 

일단 입력을 다 배열로 받고

[7]

[3,8]

[8,1,0]

[2,7,4,4]

[4,5,2,6,5]

 

위에서 부터 대각선에 해당하는 값을 아래에 더해주며 내려온다.

그럼

---

[7]

[10,15]

---

 

이런식으로 시작을 할텐데

문제는 3,8 에서 8,1,0이 있는 행으로 내려올때 1이 3과 8 양쪽의 대각선에 해당된다.

이럴 땐 max로 해결해줌

 

[7]

[10,15]

[18,max([11],[16]),15]

---

이런식으로 쭉 내려오다 보면 제일 마지마지막 줄에서 가장 큰값이 최댓값이 되겠다

 

import sys
t = int(sys.stdin.readline())
n=[list(map(int,sys.stdin.readline().split())) for _ in range(0,t)]
dp=[]
for i in range(1,t):
    for j in range(len(n[i])):
        if j == 0 :
            n[i][j] += (n[i-1][j])
        elif j==i:
            n[i][j] +=(n[i-1][j-1])
            
        else :
            n[i][j] += (max(n[i-1][j],n[i-1][j-1]))
print(max(n[t-1]))