문제 설명
값 N이 주어졌다고 가정해 봅시다. 꼭짓점에 A[0], A[1], ..., A[N-1] 라벨이 시계 방향 순서로 붙어 있는 볼록 N각형이 하나 있습니다. 이제 이 다각형을 N-2개의 삼각형으로 나누는 삼각분할(Triangulation)을 수행하려고 합니다.
각 삼각형의 값은 해당 삼각형을 이루는 세 꼭짓점 라벨의 곱으로 정의되며, 삼각분할 전체의 총 점수는 N-2개 삼각형 값들의 합입니다. 우리가 구해야 하는 것은 가능한 모든 삼각분할 방식 중에서 얻을 수 있는 최소 총 점수입니다.
예를 들어 입력이 [1,2,3]이라면 출력은 6입니다. 세 개의 꼭짓점만 있는 다각형은 이미 삼각형 자체이므로 분할이 필요 없고, 유일한 삼각형의 점수가 1 × 2 × 3 = 6이기 때문입니다.
접근 방법: 구간 동적 계획법
이 문제는 구간 단위의 동적 계획법(DP)으로 해결할 수 있습니다. dp[i][j]를 "꼭짓점 i부터 j까지로 이루어진 부분 다각형을 삼각분할할 때의 최소 점수"라고 정의하면, 두 꼭짓점 i와 j 사이에 중간 꼭짓점 k를 선택해 삼각형 (i, k, j)를 만드는 방식으로 부분 문제를 나눌 수 있습니다.
구체적인 풀이 단계는 다음과 같습니다.
- 크기 50 × 50의 2차원 배열 dp를 선언하고 모든 값을 0으로 초기화합니다.
- n := 주어진 배열 A의 크기로 설정합니다.
- 부분 다각형의 길이 l을 3부터 n까지 반복합니다.
- i := 0, j := l - 1로 시작하여 j < n을 만족하는 동안 i와 j를 함께 1씩 증가시킵니다.
- k를 i + 1부터 j - 1까지 반복하면서 다음을 수행합니다.
- dp[i][j]가 아직 계산되지 않았다면(0이라면), dp[i][j] := min(INT_MAX, dp[i][k] + dp[k][j] + A[i] * A[k] * A[j])로 갱신합니다.
- 그렇지 않다면, dp[i][j] := min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j])로 갱신합니다.
- 최종적으로 dp[0][n-1]을 반환합니다. 이것이 전체 다각형의 최소 삼각분할 점수입니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 방법을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int minScoreTriangulation(vector<int>& A) {
lli dp[50][50];
for(int i = 0; i < 50; i++){
for(int j = 0; j < 50; j++){
dp[i][j] = 0;
}
}
int n = A.size();
for(int l = 3; l <= n; l++){
for(int i = 0, j = l - 1; j < n; i++, j++){
for(int k = i + 1; k < j; k++){
dp[i][j] = min(dp[i][j] == 0 ? INT_MAX : dp[i][j],
dp[i][k] + dp[k][j] + A[i] * A[k] * A[j]);
}
}
}
return dp[0][n - 1];
}
};
main(){
vector<int> v1 = {1,2,3};
Solution ob;
cout << (ob.minScoreTriangulation(v1));
}입력
[1,2,3]
출력
6
복잡도 분석
이 알고리즘은 세 겹의 반복문을 사용하므로 시간 복잡도는 O(N³)입니다. 공간 복잡도는 dp 테이블 저장에 필요한 O(N²)입니다. N이 최대 50으로 제한되어 있으므로 충분히 빠르게 동작합니다.