1. 문제 설명

정수 삼각형

2. 문제 분석

전형적인 dp 문제로, 이전에 풀었던 값을 재활용하는 문제다. 이 경우 연결된 부모 노드(즉 상위 레벨에서 대각선으로 왼쪽, 오른쪽으로 이어진 노드) 중 최댓값을 계속해서 업데이트하면서 각 노드 별로 취할 수 있는 최댓값을 구한다.

1. dp 리스트를 만든다. 이 경우 인덱스 0이 아니라 1부터 시작하기에 수를 맞춰주었다.
2. 2층부터 이전 레벨의 대각선 방향으로 연결된 부모 노드 중 최댓값을 골라 더해준다.
3. leftmost, rightmost 노드는 각각 오른쪽, 왼쪽으로 연결된 노드만을 고를 수 있다.

• 각 dp를 가리킬 인덱스, 이전 레벨의 부모 노드에 접근할 인덱스 커서를 구하는 게 관건

3. 나의 풀이

def solution(triangle):
    dp = [0] + [0]*(sum(range(1, len(triangle)+1)))
    dp[1] = triangle[0][0]
    # level_1 (꼭대기)
    
    idx = 1
    left_offset = -2
    right_offset = -1
    # 현재 dp 인덱스 커서 및 상위 level로 이어진 인덱스 커서
    
    for i in range(1, len(triangle)):
    # level_2부터  level_n(바닥)
        idx += 1
        dp[idx] = triangle[i][0] + dp[idx+right_offset]
        # leftmost, rightmost는 각각 오른쪽, 왼쪽 대각선 위의 노드 선택
        for j in range(1, len(triangle[i])-1):
            idx += 1
            dp[idx] = triangle[i][j] + max(dp[idx+left_offset], dp[idx+right_offset])
            # 중간 노드는 연결된 왼쪽, 오른쪽 노드 중 최댓값을 선택
        idx += 1
        dp[idx] = triangle[i][-1] + dp[idx+left_offset]

        left_offset -= 1
        right_offset -= 1
        
    return max(dp)