[medium] 120. Triangle

문제

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

Triangle - LeetCode

---

풀이방법

각 row 마다 하나의 값을 찾아서 이 숫자들의 합이 최소가 되도록 하면 된다.

triangle의 각 list가 하나의 row에 있는 숫자들을 저장해둔 것 이므로 각 list에서 하나의 값을 선택해야한다.

이 때, i번째 row에서 선택된 값이 list의 j번째 숫자라면(traingle[i][j]) 그 다음 row에서 선택할 수 있는 숫자는 traingle[i+1][j] or traingle[i+1][j+1] 이 된다.

• 첫번째 아이디어: DFS -> 시간초과
  • DFS에서 몇번째 row인지에 해당하는 i, row에서 몇번째 숫자인지를 의미하는 j, 이전 row까지의 합 cursum 이렇게 세개를 전달되는 인자값으로 해서 풀면된다.
  • 시간복잡도는 O(2^N), 여기서 N=triangle.length
• 두번째 아이디어: DP
  • i번째 row, j번째 숫자까지의 최소 경로 dp[i][j]는 dp[i-1][j-1]와 dp[i-1][j] 중 작은 값과 traingle[i][j]의 합이다.
  • 시간복잡도와 공간복잡도 모두 triangle의 크기와 동일한 O(N^2)

반응형

---

코드

### 첫번째 아이디어: DFS ###

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        self.ret = float('inf')
        
        def dfs(i,j,cursum):
            if i == len(triangle):
                self.ret = min(self.ret, cursum)
                return
            cursum += triangle[i][j]
            dfs(i+1,j,cursum)
            dfs(i+1,j+1,cursum)
            
        dfs(0,0,0)
        return self.ret

### 두번째 아이디어: DP ###

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        visited = [[0]*row for row in range(1,len(triangle)+1)]
        
        visited[0][0] = triangle[0][0]
        for row in range(1, len(triangle)):
            visited[row][0] = visited[row-1][0]+triangle[row][0]
            visited[row][-1] = visited[row-1][-1]+triangle[row][-1]
            for j in range(1, row):
                visited[row][j] = min(visited[row-1][j],visited[row-1][j-1])+triangle[row][j]
        return min(visited[-1])