[Python] 프로그래머스 - 정수 삼각형

programmers.co.kr/learn/courses/30/lessons/43105

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

 

1. 먼저 triangle 배열과 같은 모양의 dp 2차원 배열을 만든다.

 

2. 마지막 줄부터 올라갈 것이므로 dp의 마지막줄은 triangle의 마지막 줄과 같게 만들어준다.

 

3. 마지막에서 두번째 줄부터해서 dp[i][j]에 (밑의 두 숫자 중 큰 값 + triangle[i][j]값)을 넣어준다.

 

4. 최종적으로 맨 윗줄에 최댓값이 저장되므로 dp[0][0]을 return해준다.

 

def solution(triangle):
    length = len(triangle)
    dp = [[0] * i for i in range(1, length + 1)]
    for i in range(length):
        dp[length - 1][i] = triangle[length - 1][i]

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

(프로그래머스 level 2)