정해는 동적 계획법이라 한다. 하지만 이런 분석또한 나쁘지 않은 것 같아 풀이를 소개한다.

해당 풀이는 분할 정복 기법(Divide and Conquer)을 활용한다.

7 3 5 1 2 6 4 라는 예제로 이해해보자. 1을 기준으로 [7 3 5]가 왼쪽, [2 6 4]가 오른쪽에 있다.

이 그룹들은 1을 활용해서 경기를 하는 것이 이득일까, 아니면 배제하고 경기를 하는 것이 이득일까?

정답은 배제하고 경기를 할 때 이득이란 점이다. 1을 끼고 할 경우, 차이값이 오히려 늘어난다. 비용에서 손해이다.

따라서 1번을 기준으로 왼쪽을 정리하고, 오른쪽을 정리한 후 합병을 하는 것이 비용상에서 이득이란 점을 알 수 있다.

왼쪽과 오른쪽 역시 부분문제로 나뉘게 된다. 우리는 이 부분문제들을 같은 원리로 해결하여 전체를 해결할 수 있게 된다.

여기서 여러가지 경우가 발생하는 것은 왜일까?? 그 이유는 처리하는 순서가 상관없을 경우에 생기게 된다.

2 1 3을 예로 들어보겠다. [1 2] 을 먼저 처리하는 것이나, [2 3]을 먼저 처리하는 것이나 사실상 최종 비용은 같다. 그래서 2가지가 된다.

이제 문제에 대한 분석이 끝났으므로 어떻게 접근할지를 생각해보자.

다음과 같은 함수와 배열을 준비한다.
int arr[a] : a번째 값을 나타낸다.
int min[a][b] : [a,b] 구간의 효율적인 비용을 저장한다.
int cnt[a][b] : [a,b] 구간을 효율적인 비용으로 처리하는 갯수를 저장한다.
int val[a][b] : [a,b] 구간을 처리했을 때의 최종 승리팀을 저장한다.
void group(int a,int b): [a,b] 구간을 위와 같은 아이디어로 정리하여 min배열과 cnt 배열, val 배열에 값을 저장시켜준다.

a=b 인 경우에 대해 한 곳에 대하여 경기를 할 수는 없으므로 min 값은 0이고, val의 값은 a의 값, cnt는 1가지인 것을 저장한다.

따라서 [a,b] 구간에서 최솟값이 i번째일 때, 다음과 같은 점화식을 세울 수 있다.

min[a][b] = min[a][i-1] + min[i+1][b] + val[a][i-1] + val[i+1][b] - 2*arr[i];
val[a][b] = arr[i];
cnt[a][b] = 2 * cnt[a][i-1] * cnt[i+1][b];

여기서 약간의 예외처리는 최솟값이 양 끝(왼쪽이거나 오른쪽)에 있는 경우인데, 그다지 어렵지 않게 처리할 수 있게 된다.

시간복잡도는 이고, 자료구조를 이용해 i의 값을 만에 찾아낸다면 으로 개선할 수 있다. 이는 데이터가 클 경우에도 충분히 효율적으로 값을 찾아낼 수 있음을 의미한다.

[Algolab 모의고사 5회] 토너먼트 풀이