1039. Minimum Score Triangulation of Polygon

1039. Minimum Score Triangulation of Polygon

https://leetcode.com/problems/minimum-score-triangulation-of-polygon/

문제

풀이

values = [1, 3, 1, 4, 1, 5] 일 때
i => values[0], j => values[5]이고 0<k<5라고 생각하면
i = 0, k = 1, j = 5일 때 삼각형 [1, 3, 5]가 만들어지고 도형 i = 1, j = 5이고 1<k<5인 도형이 만들어진다.
원하는 삼각형은 구했고 나머지 도형을 이와 같이 구하는 방법으로 하면 된다.

flg 변수는 삼각형이 만들어지지 않을 수도 있다. 즉 for문을 실행하지 못하면 삼각형을 만들어질 수 없으므로 0을 리턴한다. 그리고 삼각형(tri) 기준으로 dfs(i, k), dfs(k, j)라는 도형이 생기므로 이것을 재귀구조로 분할한다.

결과