[프로그래머스 LV 3] 정수 삼각형 (파이썬/python)

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

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

 

3레벨 문제는 아닌거같음

한 2레벨정도?

 

탑다운으로 풀면 훠얼씬 쉽게 풀 수 있지만 바텀업 연습을위해 바텀업으로 풀었음

 

dp[ i ][ j ] = max(그 위에 있는 고를 수 있는 값) + triangle[ i ][ j ]임

 

 

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