[프로그래머스 문제풀이] 정수 삼각형

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항
삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
입출력 예
triangle result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30

 (0)7(0)  
   \|\| 
 (0)3 8(0)  
   \|\|\|  
    8 1 0 

    |
    v
 (0)7(0)  
   \|\| 
(0)10 15(0)  
   \|\|\|  
    8 1 0  

위와 같은 방식으로 탐색할 때
각 단계별로 각 위치에서 얻을 수 있는 최대값을 갱신하여 새 배열에 넣는 방식으로 문제를 풀어보았다.

예를들어 3번째 줄의 1의 경우 윗줄의 3 그리고 8이 얻을 수 있는 최대값 중 큰 수를 골라 그 값에 1을 더하면 그 위치에서 얻을 수 있는 최대값을 찾을 수 있다.

그리고 왼쪽, 오른쪽 끝의 위치에서 최대값을 찾기 위한 예외를 처리하기 위해서 리스트를 N+2 만큼 선언하여 x[-1]과 x[N+1] 인덱스를 활용(값은 0), 별도의 분기구문 없이 값을 처리할 수 있도록 하였다.

def solution(triangle):
    answer = 0
    N = len(triangle)
    nmax = [0] * (N+2) # +2 for index 0, +1 for index N
    nmax[0] = triangle[0][0]
    for i in range(1, N): #[1 N]
        tmax = [0] * (N+2)
        for j in range(0,i+1): #[0 i]
            m = max(nmax[j-1], nmax[j])
            tmax[j] = m + triangle[i][j]
        nmax = tmax
    answer = max(nmax)
    return answer