Triangle

정수 트리가 주어지고 루트부터 가장 마지막 리프 노드 까지 합쳤을 때

가장 작은 합을 구하는 문제

triangle을 안건드리려고 했지만, 속도를 높이려면 triangle에 sum 값을 넣어야 할 듯

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        
        int triangleSize = triangle.size();
        
        vector<int> sum{};
        sum.push_back(triangle[0][0]);
        
        int levelSize{1};
        int count{1};
        for (int i = 1; i < triangleSize; i++)
        {
            levelSize = i + 1;
            
            for (int j = 0; j < levelSize; j++)
            {
                int value{INT_MAX};
                
                int left{j - 1};
                int right{j};
                
                if (0 <= left)
                {
                    int index = count - levelSize;
                    value = min(sum[index] + triangle[i][j], value);
                }

                if (right < levelSize - 1)
                {
                    int index = count - levelSize + 1;
                    value = min(sum[index] + triangle[i][j], value);
                }
                
                count++;
                sum.push_back(value);
            }
        }
        
        int result{INT_MAX};

        while (0 < levelSize)
        {
            result = min(sum[count - 1], result);

            count--;
            levelSize--;
        }
        
        return result;
    }
};