[LeetCode | Python] 120. Triangle

느낀점

여러 문제를 풀다보면 그래도 어떠한 문제도 익숙하게 접근하게 되는 것 같다. 너무나 편안하게 DP가 생각이 들었고 바로 구현했다.

문제

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

 

삼각형 모양으로 숫자들이 배열된 리스트가 주어졌을 때, 꼭대기에서 시작해서 맨 아래 바닥까지 이동하면서 거쳐간 숫자들의 합이 최소가 되는 경로를 찾는 문제입니다.

이동 규칙:
현재 행의 인덱스 i에 있다면, 다음 행에서는 동일한 인덱스 i 또는 바로 오른쪽 인덱스 i + 1로만 이동할 수 있습니다.

목표:
꼭대기에서 바닥까지 이동하는 모든 가능한 경로 중에서 숫자들의 합이 가장 작은 경로의 합을 반환해야 합니다.

풀이

트라이앵글 문제라고해서 배열이 아닌 것은 아니고, 보통 이런 건 첫번째부터 반복을 돌 필요가 없기 때문에 첫번째 행을 제외하고 두번째 행부터 반복한다. 각 더하기 부분을 전 위치에서 작은 값을 더해 나아가며 마지막 행중에서 가장 작은 값을 반환하면 된다.

from typing import List

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        for y in range(1, len(triangle)):
            for x in range(len(triangle[y])):
                if x == 0:
                    triangle[y][x] += triangle[y-1][x]
                elif x == len(triangle[y]) - 1:
                    triangle[y][x] += triangle[y-1][x-1]
                else:
                    triangle[y][x] += min(triangle[y-1][x-1], triangle[y-1][x])
        return min(triangle[-1])

 

결과

• 공간복잡도: $$ O(N^2) $$
• 시간복잡도: $$  O(1) $$