5. 정수 삼각형 (DP)

유형 : DP

난이도 쉬움. 

풀이 시간 : 15분

 

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

 

경로 저장도 필요 없는 문제였다.

경로 저장 없이 그냥 

 

<양 구석의 경우>

j = 0인 경우 : solution[i-1][j] + triangle[i][j]

j = len() -1 인 경우 : solution[i-1][j-1] + triangle[i][j]

아닌 경우에는 max(solution[i-1][j], solution[i-1][j-1]) + triangle[i][j] 

 

을 구해 마지막 줄 값의 최댓값을 return하면 되는 문제였다.