프로그래머스) 정수 삼각형 - lv3

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

프로그래머스

 

 

def solution(triangle):
    # 아이디어
    # dp를 이용
    # dp는 triangle의 맨 마지막에서부터 시작 -> bottom-up
    # 2번 반복문을 돌며 d[i-1][j]와 dp[i-1][j-1]을 업데이트
    # 이때 j값을 검증하여 dp업데이트 실행

    dp = [[0] * len(triangle) for _ in range(len(triangle))]
    for i in range(len(triangle[-1])):
        dp[-1][i] = triangle[-1][i]

    for i in range(len(triangle)-1, 0, -1):
        for j in range(len(triangle[i])):
            print(i, j)
            if j < len(triangle[i-1]):
                dp[i-1][j] = max(dp[i][j] + triangle[i-1][j], dp[i-1][j])

            if j != 0:
                dp[i-1][j-1] = max(dp[i][j] + triangle[i-1][j-1], dp[i-1][j-1])

    return dp[0][0]

bottom-up방식으로 풀었다.

전형적인 dp문제이지만 3단계라고 생각하기엔 매우 쉬운 난이도였다.