[프로그래머스] 43105 정수 삼각형

https://school.programmers.co.kr/learn/courses/30/lessons/43105

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

이런 형식으로 주어지는 2차원배열을 정삼각형으로 보고 맨 위에서부터 아래로 가면서 더할 때 최대값 구하는 문제이다.

DP문제였고, 두번째 줄부터 윗줄에서 최대값이랑 더한거를 업데이트 해줌으로써 했다.

즉, 첫번째 연산이 끝나면 두 번째 줄은 [10, 15]가 되고 두번째 연산이 끝나면 세번째 줄은 각각 두번째 줄에서 가져올 수 있는 것 중 최대값을 가져와서 [18, 16, 15]가 된다. 이런식으로 반복하면 업데이트된 삼각형은

         [7]
      [10, 15]
    [18, 16, 15]
  [20, 25, 20, 19]
[24, 30, 27, 26, 24]

이렇게 되고 그 중 최대값인 30을 출력해줬다.

def solution(triangle):
    answer = 0
    
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            if j == 0:
                triangle[i][j] += triangle[i-1][j]
            elif j == len(triangle[i])-1:
                triangle[i][j] += triangle[i-1][j-1]
            else:
                triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])        
    
    return max(triangle[-1])