백준2262 토너먼트 만들기

작성일 | In

문제 링크

  • http://icpc.me/2262

사용 알고리즘

  • DP

시간복잡도

  • O(n3)

풀이

dp[i][j] = i번째부터 j번째 사람까지만 고려했을 때 정답 으로 정의합시다.
점화식은 다음과 같이 나오게 됩니다. dp[i][j] = min(dp[i][k] + dp[k+1][j] + something...)
위 점화식은 i부터 k까지와 k+1부터 j까지에서 각각 토너먼트를 진행한 뒤, 두 명의 승자를 마지막에 경쟁을 시키는 것을 의미합니다. 그러면 something은 두 개의 토너먼트의 승자들의 랭킹 차이가 되겠네요. 당연히 i <= k < j를 만족해야 합니다.

본격적으로 구현을 하기 전에, 구현을 조금 더 편하게 해줄 배열을 하나 만들어줍시다.
a와 b가 대결했을 때의 승자를 winner[a][b]에 저장해줍시다.

점화식을 채우는 방법을 알아봅시다.
만약 i, j가 같다면 랭킹 차이가 0이므로 0을 넣어주면 됩니다.
그렇지 않은 경우에는 k를 i부터 j-1까지 순회시키면서 dp[i][k] + dp[k+1][j] + | winner[i][k] - winner[k+1][j] |의 최솟값을 구해주면 됩니다.

(이 문제) 혹은 (이 문제)와 유사하게 구현하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

int dp[300][300];
int winner[300][300];

int solve(int i, int j){
	int &res = dp[i][j];
	if(res != -1) return res;
	if(i == j) return res = 0;

	res = 1e9+7;
	for(int k=i; k<j; k++){
		res = min(res, solve(i, k) + solve(k+1, j) + abs(winner[i][k] - winner[k+1][j]));
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<int> v(n);
	for(int i=0; i<n; i++) cin >> v[i];

	for(int i=0; i<n; i++){
		winner[i][i] = v[i];
		for(int j=i+1; j<n; j++){
			winner[i][j] = min(winner[i][j-1], v[j]);
		}
	}

	memset(dp, -1, sizeof(dp));
	cout << solve(0, n-1);

}