k 제한이 없다고 생각하고 문제를 보자.
S={A1, …, An} 으로 놓고 DP식을 세우면 아래처럼 될 것이다.
즉, 전체 지루함 = 전체를 두 그룹으로 나눠서 각 그룹에서 승자를 뽑을때까지 생기는 지루함 + 두 그룹의 최종 승자끼리 붙는 매치의 지루함 이다. 그런데 최종 매치의 지루함은 두 그룹의 최종 승자인 max(S1)과 max(S-S1)에만 관련이 있고, 나머지들은 어떻게 배치되는 상관이 없다. 그리고 각 그룹에서 승자를 뽑을때까지 생기는 지루함을 줄이기 위해서는 그 그룹안에 최강자와 최약자 사이의 갭이 작은 것이 유리하다.이 두가지를 조합하면, S를 S1과 S-S1으로 쪼개면서 max(S1)=X이고 max(S-S1)=max(S)=Y가 되게 한다면, S1에는 X보다 작은 Ai를 모두 넣고, S-S1에는 X보다 큰 Ai를 모두 넣는 것이 가장 좋은 방법이다.
사실 엄밀하게 증명하려면 조금 더 길어져야 할거 같은데.. 직관적으로 당연해보이니 생략..
높이 제한이 없다면. 그냥 제일 약한 선수 둘이 첫 매치를 치루고, 그 승자가 그다음 강한 선수와 다음 매치를 치루고, .. 이런식으로 반복하는 계단식 토너먼트 구성이 가장 최적이라는 것도 알수 있다.
그러면 이제 A가 정렬되어서 A1<A2<…<AN 이 되어있다고 생각하면.. 결국 Ai중 어디를 기준으로 두개의 작은 구간으로 나눌 때 최적이 되는지만 결정하면 된다. dp[i][j]를 Ai,…,Aj에 대해서 지루함의 최소값이라고 하면
구간 분할 방식에 관한 DP 에서 흔히 보게 되는 형태로 쓸 수 있다.
구간 분할 방식에 관한 DP 에서는 min_k{dp[i][k] + dp[k+1][j] + C[i][j]} 형태로 점화식을 만들 수 있고, C[i][j]가 사각부등식과 단조성을 만족하면
크누스 최적화를 적용할 수 있지만, A[j] - A[k] 는 일단 k가 포함되어 있어서 그대로는 잘 안될거 같다.
식을 조금 바꿔보자.. dp2[i][j] = dp[i][j] - A[j]라고 바꿔보면, dp2[i][j] = min_k{dp2[i][k] + dp[k+1][j] + 2A[j]} 가 된다. A가 단조증가하도록 정렬되어있으니 C[i][j] = 2A[j] 는 필요한 속성을 다 만족하므로 크누스 최적화를 적용할 수가 있다. 그러면 O(n^2)에 계산 가능.
여기에 높이 제한을 추가해서 두어서 다시 쓰면, dp[h][i][j]를 Ai,…,Aj 에 대해서 h이하의 높이로 트리를 구성할때의 지루함의 최소값이라고 하자. 그러면 dp[h][i][j] = min_k{dp[h-1][i][k] + dp[h-1][k+1][j] + A[j] - A[k]} 로 쓸 수 있다. 같은 방식으로 크누스 최적화를 적용해서, K개의 n*n 테이블을 각각 O(n^2)에 채우면 된다. 총 시간은 O(K*n^2).
dp2[K][0][N-1]을 구하고 난 다음에 바로 출력하는 실수를 하지 말자. A[N-1]을 더해줘야 dp[K][0][N-1]이 된다.
다 풀고서 다른 사람들의 코드를 보니, 크누스 최적화의 필요조건을 맞춰주기 위해서 dp를 dp2로 바꿔주는 작업을 안하고 그냥 dp를 바로 계산하는 코드들도 제대로 돌아가는 것을 확인했다.. 사실 크누스 최적화를 공부할때 증명을 찾아보고 제대로 이해한것이 아니라, 그냥 필요조건만 암기한거라서 왜 저렇게 해도 돌아가는 건지 이해가 불가능하다 ㅜ