[Leetcode/파이썬] 120. Triangle

Triangle

---

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

 

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]
Output: -10

 

Constraints:

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -104 <= triangle[i][j] <= 104

 

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

 

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        tbl = [[0 for _ in range(len(triangle[i]))] for i in range(len(triangle))]
        tbl[0][0] = triangle[0][0]

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

처음에는 아주 큰 수 (ex. $10 ** 8$)를 넣어서 실행했었는데 굳이 그럴 필요가 없다는 것을 여러번 풀어 보면서 확인할 수 있었다. 사실 삼각형이기 때문에 len(triangle[i]) 대신 $i+1$ 을 넣어도 되는데, 더 쉽게 이해하기 위해서 각 배열의 길이로 표기하였다. 이 문제는 길을 따라 갈때 어떻게 이동하는지에 대해서 고민을 해보면 쉽게 해결할 수 있다. 리트코드에서 문제 뿐만 아니라 백준이나 다른 곳에서도 많이 볼 수 있는 유형의 문제이니 참고하면 더욱 도움이 될 듯 하다. 

삼각형 내의 이동에서 가장 앞과 가장 뒤는 도달할 수 있는 방향이 하나이다. 그 전 배열에서 가장 앞 부분과 가장 뒷 부분에서 그대로 타고 내려오는 수 밖에 없다. 그렇기 때문에 그냥 고민하지 말고 if 문에서 가장 앞과 가장 뒤는 제거하고 가자. 가장 앞은 인덱스 0, 가장 뒤는 인덱스가 i 인 상황이다. 여기서 주의할 점은 0인 상황에서는 j, i 인 상황에서는 j-1 을 받아온 후 현재 값을 더해줘야 한다는 점이다. 이후 가운데 부분은 이전 테이블의 두 갈래의 방향에서 수를 받아온 후 더 작은 값을 구별하고, 이후 현재값을 더한다. 이러면 현재 위치에서의 최소값을 구할 수 있다. 그리고 마지막에 테이블의 가장 아래부분의 최소값을 return 하면 된다. 

사실 이 문제를 풀면서 return 할때 min(tbl[-1]) 이 아니라 min(triangle[-1]) 을 해서 문제를 10분 넘게 고민했었다. 다른 분들은 이런 실수 하지 마시길 허허...