[프로그래머스] 정수 삼각형.py

https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 

코딩테스트 연습 - 정수 삼각형

 

기본적인 DP(Dynamic Programming)문제 입니다. 

어떤 경로로 가는것이 최고의 합이 나오는지 궁금한 문제 입니다.

 

예시 풀이

첫번째줄에서 두번째줄로 갈때 7 에서 3 또는 8 을 고를때 8을 고르는게 좋을 수 있지만 8을 선택하면 세번째줄의 8을 고르지 못할 수 있습니다. 만약 세번째줄의 8이 100이었으면 그때그때 최선의 숫자를 고르는것은 좋지 않은 선택이 될 수 있습니다.

따라서 가능한 경우의 수를 모두 구하는것이 좋습니다. 

위에서 아래방향으로 내려올 경우 3과 8의경우 둘다 맨 왼쪽, 맨 오른쪽값이기 때문에 7을 고를 수 밖에 없습니다. 이런 예외를 처리 해줘야 하는게 어려울 수 있으므로 반대로 아래에서 위로 올라가면서 더해주는 방법을 선택 했습니다. DP는 그때그때 전단계의 최선의 답을 저장해두고 다음에도 사용하는 방법 입니다.

밑에서 두번째 2의 경우 5가 최선. 따라서 2까지 올때 최선의값은 (5+2) = 7이 될것입니다.

밑에서 두번째 7의 경우에도 5가 최선 (5 + 7) = 12가 될것입니다. 이런식으로 4, 4에 최선의값을 할당해주고

밑에서 세번째 8은 지금 밑에서 나온 2와 7의 최선의 값 7, 12 중에 12를 뽑아서 12 + 8 = 20이 될것이고 

이런식으로 올라가다보면 7은 최선의값 30이 나오게 됩니다.

 

코드

def solution(triangle):
    
    length = len(triangle)
    triangle = list(reversed(triangle))
    dp = [[] for _ in range(length)]
    dp[0] = triangle[0]
    for i in range(1, length):
        for j in range(len(triangle[i])):
            dp[i].append(max(dp[i-1][j],dp[i-1][j+1]) + triangle[i][j])
    return dp[-1][0]