[프로그래머스] 정수 삼각형 - 파이썬(python)

 

나의 풀이

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

전형적인 bottom up 동적프로그래밍 문제이다.

dp[] 에는항상 dp[i][j] 까지의 최댓값 경로가 저장되어 있다.

따라서 dp[i][j] 를 구하려면, dp[i-1][j-1] 와 dp[i-1][j] 둘 중 더 큰값을 나의 값에 더해주면 된다.

만약 한 줄에서 첫번째 값(j=0)이라면, 항상 dp[i-1][0] 에서만 이어지며,

마지막 값(j=i)이라면, 항상 dp[i-1][i-1] 에서만 이어진다.

 

삼각형의 바닥부분은 각자의 경로로 왔을 때의 최댓값들의 모음이 되게 된다.

이 중 가장 큰 값을 리턴하면 된다.