Written by 최태열
on 

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

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

코드

def solution(triangle):
    triangle = [[0]+i+[0] for i in triangle]
    
    for x in range(1,len(triangle)):
        for y in range(1,len(triangle[x])-1):
            triangle[x][y]+=max(triangle[x-1][y-1],triangle[x-1][y])
    return max(triangle[-1])

dp 문제다.

정수 삼각형의 각 위치의 값은 다음과 같은 점화식으로 나타난다.

triangle[x][y]=triangle[x][y]+max(triangle[x-1][y],triangle[x-1][y-1])

맨 왼쪽과 맨 오른쪽은 위에 있는 값을 그대로 가져오기 때문에

예외처리를 해주기 위해서 triangle 양 옆에 0을 붙혀준다.

Discussion and feedback