[파이썬/python] 백준 1932번 : 정수 삼각형(🥈1)

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

for i in range(1,len(tri)):
    for j in range(len(tri[i])): 
        if j == 0:
            tri[i][j] += max(tri[i-1][0:j+1])
        else:
            tri[i][j] += max(tri[i-1][j-1:j+1])
print(max(tri[-1]))

연속합이랑 RGB는 다른 풀이를 참고하고 풀었는데 드디어 아무것도 안 보고 풀었다..

 

1층에서부터 이전 층에 있는 수를 더해주는 식으로 풀어야 한다. 현재 위치해 있는 수의 인덱스가 n이라고 하면, 이전층에 있는 n-1, n에 위치한 인덱스를 더할 수 있다.

그래서 tri[i][j]에 위치에 있는 수를 tri[i-1][j-1:j+1] 중에서 가장 큰 수를 누적해서 더해주는 식으로 풀이하였다.

과정이 끝나면 마지막 층의 가장 큰 수를 출력하였다.