[ leetcode ] 120. Triangle

해당 문제는 십진수를 담고 있는 이차원 배열로 주어진 삼각형 형태의 꼭지에서 삼각형의 제일 바닥까지 경로의 합 중 가장 작은 것을 반환하는 문제입니다. 만약 삼각형의 row번째에서 index의 원소를 택했다면, row+1번째에서는 index, index+1로만 움직일 수 있습니다.

처음에는 삼각형 제일 위에서 아래로 BFS방식으로 모든 경로를 탐색하려 했으나, 시간 초과가 발생하여 가지 치기가 가능한 경우를 생각했지만 다음 row에 감소하는 경우가 있으므로 중간 경로에서 가지치기를 할 수 없었습니다.

이에 반대로 올라가는 경우를 생각해보니, 문제에서 주어진 제약 조건처럼 O(n)의 공간 복잡도를 가지면서 처리를 하려면 DP(Dynamic Programing)로 해결해야 했고, 마지막 줄 기반으로 index, index+1중 작은 것을 택하고 거기서 갈 수 있는 전 줄은 index밖에 없으니 

dp에는 삼각형의 마지막 줄이 들어있다고 생각하고, row는 그 전 줄을 가리킨다면, 아래 식이 완성됩니다.

#define min(a,b)((a) > (b) ? (b) : (a))

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int rows = triangle.size();
        vector<int> dp = triangle.back();

        for (int row = rows-2; row >= 0; row--) {
            for (int col = 0; col <= row; col++) {
                dp[col] = min(dp[col], dp[col+1]) + triangle[row][col];
            }
        }

        return dp[0];
    }
};

공간 복잡도는 정확히 O(n)만큼 사용하면서 시간 복잡도도 전체 삼각형을 한번씩만 순회하면 되므로 O(n^2)이 사용됩니다.