1130. Minimum Cost Tree From Leaf Values

https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/

Minimum Cost Tree From Leaf Values - LeetCode

---

트리 자료구조에 얽매여서 생각하면 문제가 어려워진다. 

 

리프노드와 논리프노드를 제외한다면, 트리 개념이 그닥 필요하지 않은 문제. 핵심은 큰 숫자의 곱셈 횟수를 최소화 하는 것 이다.

 

https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/discuss/457914/JavaScript-Solution-DP-and-Greedy

 

var mctFromLeafValuesGreedy = function(arr) {
    let cost = 0;
    while (arr.length>1) {
        let minProduct = Number.MAX_VALUE;
        let minId = -1;
        for (let i=0;i<arr.length-1;i++) {
            let curProduct = arr[i] * arr[i+1];
            if (curProduct < minProduct) {
                minProduct = curProduct;
                minId = arr[i]<arr[i+1]?i:i+1;
            }
        }
        cost+=minProduct;
        arr.splice(minId, 1);
    }
    return cost;
}