[LeetCode] 120. Triangle

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

Triangle - LeetCode

Triangle - Medium

 

위 예시와 같이 삼각형모양으로 수가 나열되어 있다. 이 때, 가장 위에서부터 출발하여 삼각형 아래줄의 왼쪽 또는 오른쪽으로 이동할 수 있다고 할 때, 경로상에 있는 모든 수들의 합이 가장 작을 때를 구하는 문제다.

 

흔히 보이는 dp문제다.

2
3	4
6	5	7
4	1	8	3

일단 가장 위의 2 위치에 있을 때, 다음엔 3 또는 4로 갈 수 있고,

5의 위치에 있다면 1 또는 8로 갈 수 있다.

즉 (i, j) -> (i+1, j) 또는 (i, j) -> (i+1, j+1)로 이동할 수 있다.

반대로 (i, j)로 올 수 있는 방법은 (i-1, j-1) 또는 (i-1, j) 에서 이동하는 방법인데,

이를 이용하면 (i, j) 에서 가장 작은 경로합은 (i-1, j-1) 과 (i-1, j)의 경로 중 더 작은 경로에서 오는 경우가 된다.

즉, dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j]) 가 된다.

 

전체 풀이 코드

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int m = INT_MAX;
        for (int i=1; i<triangle.size(); i++) {
            triangle[i][0] += triangle[i-1][0];
            triangle[i].back() += triangle[i-1].back();
            for (int j=1; j<triangle[i].size()-1; j++) triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]);
        }
        for (int n:triangle.back()) m = min(m, n);
        return m;
    }
};