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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105

문제 접근

삼각형의 두번째 줄까지 먼저 만들어놓고, 세번째 줄부터는 왼쪽 위와 오른쪽 위 원소 중 최대값을 선택해서 더해나가는 것을 누적으로 진행함

소스 코드

from typing import List


def solution(triangle: List[List[int]]) -> int:
    answer = 0
    top = triangle[0][0]
    if len(triangle) == 1:
        return top

    max_triangle = [[top], [triangle[1][0] + top, triangle[1][1] + top]]

    print(list(range(2, len(triangle))))
    for row in range(2, len(triangle)):
        max_triangle.append([])
        for col in range(len(triangle[row])):
            lower = col - 1 if col - 1 >= 0 else 0
            upper = col + 1 if col + 1 <= len(triangle[row]) else len(triangle[row])
            search_list = max_triangle[row - 1][lower:upper]
            val = max(search_list) + triangle[row][col]

            max_triangle[row].append(val)
            answer = max(val, answer)

    return answer