[Python] 프로그래머스(Lv2) - 정수 삼각형

안녕하세요 :)

지난글에 DP로 푸는 문제를 올렸었는데요! 그래서 DP문제 하나를 더가져와봤습니다

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

문제에서 대각선 방향으로 한칸 오른쪽 또는 왼쪽으로만 이동가능하다고 나와있습니다.

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

triangle 배열이 이렇게 주어진다면 열이 같거나 또는 열이 하나 큰 쪽으로 이동되록 구현했습니다.
예를 들어서, 지금 값이 2행의 3이라면 8(열이 같음)이나 1(열이 하나 큼)로 이동이 가능하겠죠.

def solution(triangle):
    size = len(triangle)
    d = [[-1] * size for _ in range(size)]
    d[0][0] = triangle[0][0]

    for n in range(1, size):
        for i in range(len(triangle[n])):
            d[n][i] = triangle[n][i] + max(d[n-1][i-1], d[n-1][i])

    return max(d[-1])