[Leetcode] 120. Triangle 문제풀이

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

Triangle - LeetCode

문제 내용

삼각형 배열에서 탑에서 바닥까지 경로를 구할 때 경로의 합이 최소인 값을 구하는 문제

경로는 i, i + 1칸 움직일 수 있다.

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).

 

문제 풀이

트리 형태로 구성되어 있어서 완전 탐색을 하면 중복되는 부분이 많다.

그래서 중복되는 부분을 1번만 계산할 수 있게 dp를 사용해서 풀 수 있다.

 

dp를 처음에는 2차원 배열로 쉽게 생각할 수 있지만

1차원만 배열만 있으면 구할 수 있다.

 

top down approach 를 하면 2차원이지만,

bottom up approach 를 생각하면 1차원으로 생각할 수 있다.

 

i, i+1 을 내려가는 방식이 아니라 올라가는 방식으로 생각하면

i, i+1 중에 min값이 위쪽의 i값이 된다.

 

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int row = triangle.size();
        
        vector<int> dp(triangle[row-1].begin(), triangle[row-1].end());
        
        for (int y = row-2; y >= 0; --y) {
            for (int x = 0; x < triangle[y].size(); ++x) {
                dp[x] = min(dp[x], dp[x+1]) + triangle[y][x]; 
            }
        }
        
        return dp[0];
    }
};