[LeetCode] 1039. Minimum Score Triangulation of Polygon

문제 출처: https://leetcode.com/problems/minimum-score-triangulation-of-polygon/

Minimum Score Triangulation of Polygon - LeetCode

문제

n개의 꼭짓점에 정수 값이 할당된 다각형을 갖고 있다. 꼭짓점의 값을 갖고 있는 배열 value가 주어진다.(시계방향 순)

 

주어지는 다각형을 n-2개의 삼각형으로 나누려고 한다. 각 삼각형은 꼭지점 값의 곱을 통해 해당 삼각형의 값을 계산할 수 있고, 이 삼각형의 값의 합을 통해 전체 점수를 구할 수 있다.

 

주어진 다각형에서 얻을 수 있는 전체 점수 중 가장 작은 값 을 반환하라.

예제

Input: values = [1,2,3]
Output: 6
Explanation: The polygon is already triangulated, and the score of the only triangle is 6.

Input: values = [3,7,4,5]
Output: 144
Explanation: There are two triangulations, with possible scores: 3*7*5 + 4*5*7 = 245, or 3*4*5 + 3*4*7 = 144.
The minimum score is 144.

Input: values = [1,3,1,4,1,5]
Output: 13
Explanation: The minimum score triangulation has score 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13.

풀이

다각형에서 만들 수 있는 모든 삼각형의 케이스를 한 번에 찾는다는 것은 어려운 문제로 보이므로, 주어진 다각형에서 한 개의 삼각형을 그리는 문제를 생각해보자.

 

아래의 그림은 육각형에서 한 변을 기준으로 삼각형을 그린 그림이다.

만든 삼각형을 제외하면 최초의 다각형이 1개 또는 2개의 도형으로 나누어지는 것을 볼 수 있다.

 

나누어진 도형을 보면, 원래의 도형보다 작은 수의 꼭지점을 갖는 다각형이다. 최초의 문제보다 더 작은 문제가 되었음을 알 수 있다. 문제 해결 실마리를 찾은 듯하다.

 

여기서 한 가지 생각해볼 것은 "그렇다면 모든 변에 대해서 이 과정을 거쳐야 하는가?" 이다. 답은 No 이다. 다음의 그림을 살펴보자.

왼쪽 그림은 이전에 자른 다각형 중 마지막 도형에 대해서 동일한 방식으로 삼각형을 만드는 것을 표현한 것이고, 오른쪽 그림은 원래의 육각형에서 기존과는 다른 변을 선택하여 삼각형을 만드는 것을 표현한 것이다.

 

빨간색 선이 만드는 삼각형과 보라색 선이 만드는 삼각형의 형태가 완전히 동일하다는 것을 알 수 있다. 이러한 이유로 한 단계에서 모든 변을 체크하지 않고 임의의 한 변만 선택하더라도 재귀적 반복을 통해서 모든 삼각형을 체크할 수 있다는 것을 알 수 있다.

 

이를 코드로 작성하면 다음과 같다.

// N각형에 대해서, 초기 left = 0, right = N-1
function calcPolygonScore(values, left, right) {
    // base case: 꼭지점이 3개 미만이라면 삼각형이 아니므로 0 반환
    if (left + 2 > right) {
        return 0;
    }
    // 꼭지점이 3개라면, 더 이상 나눌 수 있는 형태가 아니므로 값을 계산하여 반환
    if (right - 2 == left) {
        return values[left] * values[left+1] * values[left+2];
    }

    // left와 right를 변을 기점으로 만들 수 있는 삼각형을 만들고
    // 만들어진 삼각형을 기준으로 다각형을 나누어 점수 계산
    let score = Infinity;
    for (let i = left+1; i < right; i++) {
        const score_1 = calcPolygonScore(values, left, i);
        const score_2 = calcPolygonScore(values, i, right);
        const cur = values[left] * values[i] * values[right];
        score =  Math.min(score, score_1 + score_2 + cur);
    }
    return score;
}

이 코드에서 한 가지 트릭은 삼각형을 만들 기준이 되는 변을 선택이 values배열의 0th와 N-1th라는 것이다.

 

코드에서 한 가지 개선할 수 있는 곳이 있다. 코드를 보면, 재귀를 수행하는 과정에서 파라미터의 left와 right가 어떠한 변경 없이 동일하게 전달되는 것을 볼 수 있는데, 이로 인해서 동일한 지점에 대한 계산을 여러 번 수행하는 문제를 생각할 수 있다. 이 문제를 DP를 통해서 해결한 코드는 다음과 같다.

const dp = new Array(values.length).fill(0).map(val => new Array(values).fill(null));

var calcPolygonScore = function (values, left, right) {
    if (left+2 > right) { return 0; }

    if (dp[left][right]) { return dp[left][right]; }

    if (right - 2 == left) {
        dp[left][right] = values[left]*values[left+1]*values[left+2];
        return dp[left][right];
    }

    let score = Infinity;
    for (let k = left+1; k < right; k++) {
        const score_1 = calcPolygonScore(values, left, k);
        const score_2 = calcPolygonScore(values, k, right);
        const cur = values[k] * values[left] * values[right];
        score = Math.min(score, score_1 + score_2 + cur);
    }

    dp[left][right] = score;

    return dp[left][right];
}

Github: 1039.js

opwe37/Algorithm-Study