[Algorithm] 프로그래머스 정수 삼각형 | 파이썬 (DP, Dynamic Programming)

※ 정수 삼각형

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

프로그래머스

 

문제 해결 TIP

우선 예제 입력에 대해 30이 어떻게 나왔는지 파악해보자. 맨 위인 7에서 부터 밑으로 내려가며 합해준다. 두 번째 줄은 가운데가 없고 양끝만 존재하므로 10, 15가 된다. 세 번째 줄부터는 바로 위(두 번째 줄)에서 얻을 수 있는 숫자가 2가지(왼쪽 10, 오른쪽 15) 경우의 수인 가운데가 존재한다. 이때, 더 큰 숫자인 16으로 교체가 된다. 이를 반복하여 알 수 있는 것은 트리의 가장자리 양 끝은 바로 위의 노드를 이어받고, 2가지 경우가 존재할 수 있는 노드들은 max값으로 대체되는 것이다. 따라서 1) 왼쪽 가장자리 끝 2) 2가지 경우가 존재하는 가운데 3) 오른쪽 가장자리 끝으로 총 3가지 경우의 수를 얻을 수 있다.

최종 dp테이블은 다음과 같다.

전체 코드

def solution(triangle):
    dp = triangle
    dp[1][0] = dp[0][0] + dp[1][0]
    dp[1][1] = dp[0][0] + dp[1][1]
    #dp =[[7], [10, 15], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

    for i in range(2,len(triangle)):
        for j in range(len(triangle[i])):
            if j == 0:
                dp[i][j] = dp[i][j] + dp[i-1][j]
            elif j == len(triangle[i])-1:
                dp[i][j] = dp[i][j] + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i][j] + dp[i-1][j], dp[i][j] + dp[i-1][j-1])
    return max(dp[-1])