내일은 알고리즘

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

DP 유형의 문제입니다.

삼각형을 좌측으로 정렬해 계단 형태의 2차원 배열로 생각하고 풀면 쉽게 풀립니다.

삼각형을 내려오는 방향은 좌하단, 우하단 두가지만 가능합니다.

즉 내 위치가 i 번째 행의 j 번째 열이라면 내 위치로 오기 위해선 반드시 (i-1, j-1) 또는 (i-1, j)을 지나야 합니다.

따라서 해당 위치로 오는 경로의 최댓값은 (i-1, j-1) 또는 (i-1, j)로 가는 경로 중 큰 값에 해당 위치의 값을 더한 값이 됩니다.

마찬가지 규칙이 처음 0,0에서부터 시작해 연산해주면 됩니다. 단, 가장 좌측 (i행 0열)과 가장 우측 (i행의 i열)은 내려오는 경로가 한가지만 가능하므로 따로 계산해주어야합니다.

우리가 찾아야할 최댓값은 삼각형의 높이 == i번째 행의 원소중 최댓값입니다. 

def solution(triangle):
    answer = 0
    height = len(triangle)
    dp = [[0 for i in range(height)] for j in range(height)]

    dp[0][0] = triangle[0][0]

    for i in range(1, height):
        dp[i][0] = dp[i - 1][0] + triangle[i][0]
        for j in range(1, i):
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
        dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]

    for i in range(height):
        answer = max(answer, dp[height - 1][i])
    
    return answer