[프로그래머스 Lv.3] 정수

by 



def solution(triangle):
    
    height = len(triangle) # 삼각형의 높이
    
    dp_list = ((0)*height for _ in range(height)) # DP 리스트
    
    dp_list(0)(0) = triangle(0)(0)
    
    for i in range(1,height):
        for j in range(len(triangle(i))):
            if j==0: # 가장 왼쪽 원소인 경우
                dp_list(i)(j) = dp_list(i-1)(0) + triangle(i)(0)
            elif i==j: # 가장 오른쪽 원소인 경우
                dp_list(i)(j) = dp_list(i-1)(j-1) + triangle(i)(j) 
            else:
                dp_list(i)(j) = max(dp_list(i-1)(j-1)+triangle(i)(j), dp_list(i-1)(j)+triangle(i)(j))
               
    max_value = max(dp_list(-1))

    return max_value

이 문제는 동적 프로그래밍 문제의 대표적인 예인 정수 삼각형입니다.

대각선 방향으로만 이동할 수 있을 때 전달되는 숫자의 합을 최대화하는 문제오전.

'추천 관련글,