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

1. 문제

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

2. 풀이

dp를 이용하여 문제를 해결합니다. 이전 합들 중에서 자신에게 올 수 있는 값 중 더 큰 값과 자신의 값을 더해주는 과정을 반복합니다.

def solution(triangle):
    sum_list = [[0] * (len(triangle)) for _ in range(len(triangle))]
    sum_list[0][0] = triangle[0][0]

    for row in range(1, len(triangle)):
        sum_list[row][0] = triangle[row][0] + sum_list[row - 1][0]
        sum_list[row][row] = triangle[row][row] + sum_list[row - 1][row - 1]
        for col in range(1, row):
            sum_list[row][col] = triangle[row][col] + max(sum_list[row - 1][col - 1], sum_list[row - 1][col])

    return max(sum_list[row])

PREVIOUS[프로그래머스] 가장 먼 노드

NEXT[프로그래머스] K번째수 풀이