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

https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3

DP를 이용하여 최대값을 나타내는 경로를 선택한 합을 출력하는 문제이다.

코드

def solution(triangle):
    answer = 0
    triangle = triangle[::-1]
    for i in range(len(triangle)-1): # 층수 0,1,2 ...
        for j in range(len(triangle[i])-1): # index
            triangle[i+1][j] += max(triangle[i][j], triangle[i][j+1])
    return triangle[-1][0]

설명

triangle 배열을 거꾸로 뒤집은 다음, 한층씩 이동하며 왼,오른 쪽 중에서 큰 수를 아래층에 더해가는 방식으로 구현하였다.

결국 마지막 층에는 하나의 원소가 남아있을 것이고, 그것을 리턴하면 된다.