[pro42628][Level 3] 정수 삼각형

개요

기본적인 DP를 이용해서 풀이하였다.
같은 레벨의 노드중에서 가장 좌측에 위치한 노드인 경우와 가장 우측에 위치한 노드인 경우만 따로 처리해주고, 나머지는 연결된 상위 레벨의 노드와 비교하여 더 큰 값을 이용해 구해주면 된다.

코드

def solution(triangle):
    n = len(triangle[-1])
    mem = [[-1] * n for _ in range(n)]
    for i in range(n): # 층 수
        for j in range(i+1): # 너비
            if i == 0: mem[i][i] = triangle[i][i]
            else: 
                if j == 0: mem[i][j] = mem[i-1][j]+triangle[i][j]
                elif j == i: mem[i][j] = mem[i-1][j-1]+triangle[i][j]
                else: mem[i][j] = max(mem[i-1][j]+triangle[i][j], mem[i-1][j-1]+triangle[i][j])
    return max(mem[-1])