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

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

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

 

 

< 문제 설명 >

위에서 부터 차례대로 합해 가장 큰 합를 리턴한다.

이때, 두 방향으로밖에 못내려감. 7 -> 3, 8      3 -> 8, 1

 

 

< 문제 이해 >

내려가면서 더하고, 더한 값이 원래 값보다 작으면 원래 값을 사용하는 dp 문제!

 

 

< 문제 풀이 >

def solution(triangle):
    dp = [[0]*i for i in range(1,len(triangle)+1)]	# dp배열 미리 만들어 놓음
    dp[0][0] = triangle[0][0]				# 맨 꼭대기
    
    for i in range(0, len(triangle)-1):
        for j in range(i+1):
            dp[i+1][j] = max(dp[i][j] + triangle[i+1][j], dp[i+1][j])
            dp[i+1][j+1] = max(dp[i][j] + triangle[i+1][j+1], dp[i+1][j+1])
    
    return max(dp[len(triangle)-1])