[LeetCode]Triangle

https://leetcode.com/problems/triangle/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

triangle 리스트가 주어질 때 위에서부터 아래로 이동시 가장 최소가 되는 경로의 합을 구하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        triangle_len = len(triangle)

        for i in range(1, triangle_len):
            for j in range(i+1):
                if j == 0:
                    triangle[i][j] = triangle[i][j] + triangle[i-1][j]
                elif j == i:
                    triangle[i][j] = triangle[i][j] + triangle[i-1][j-1]
                else:
                    triangle[i][j] = triangle[i][j] + min(triangle[i-1][j-1], triangle[i-1][j])


        return min(triangle[-1])

접근 방법

1. DP를 활용해 풀이할 수 있는 문제입니다.
2. 각 높이별로 존재하는 숫자만큼 이중 순회를 반복합니다.
   1. 만약 가장 왼쪽에 있는 숫자라면 현재 숫자와 i-1, j에 있는 숫자를 더합니다.
   2. 만약 가장 오른쪽에 있는 숫자라면 현재 숫자와 i-1, j-1에 있는 숫자를 더합니다.
   3. 그 외의 경우에는 현재 숫자에서 i-1,j-1 혹은 i-1,j 중 작은 값과 숫자를 더합니다.
3. 반복을 마치면 마지막 열에 가장 적은 숫자가 최소 경로의 합이 됩니다.

Top - Bottom 방식으로 숫자를 누적해나가면서 쉽게 풀이할 수 있는 DP 기본 문제입니다.