백준 2262번 토너먼트 만들기

문제 링크입니다: https://www.acmicpc.net/problem/2262

2262번: 토너먼트 만들기

그리디 알고리즘 혹은 DP 알고리즘을 통해 풀 수 있는 문제였습니다.

저는 우선 그리디 알고리즘으로 풀었고 DP로도 풀 예정입니다.

 

그리디하게 접근하자면 아래와 같습니다.

1. 랭킹이 제일 낮은 사람은 무조건 팀으로 묶이고 떨어지는 것이 유리합니다.

2. 랭킹이 제일 높은 사람은 마지막에 묶이지 않고 홀로 남습니다.

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;
	vector<int> v(N + 2, 0);
	for (int i = 1; i <= N; i++)
	{
	cin >> v[i];
	}
	int result = 0;
	// 꼴찌부터 쌍으로 묶는다
	for (int i = N; i > 1; i--)
	{
	int j;
	for (j = 1; j <= N; j++)
	{
	if (v[j] == i)
	{
	break;
	}
	}
	result += v[j] - max(v[j - 1], v[j + 1]);
	for (; j <= N; j++)
	{
	v[j] = v[j + 1];
	}
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

(수정: 2019.11.08 23:31)

DP로도 풀었습니다.

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <cstring>
	using namespace std;
	const int MAX = 256;
	const int INF = 987654321;
	int winner[MAX][MAX];
	int cache[MAX][MAX];
	// start ~ end 경쟁 시킨다
	int func(int start, int end)
	{
	int &result = cache[start][end];
	if (result != -1)
	{
	return result;
	}
	if (start == end)
	{
	return result = 0;
	}
	result = INF;
	for (int i = start; i < end; i++)
	{
	result = min(result, func(start, i) + func(i + 1, end) + abs(winner[start][i] - winner[i + 1][end]));
	}
	return result;
	}
	int main(void)
	{
	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];
	// i ~ j 중 랭킹 높은 인원
	for (int j = i + 1; j < N; j++)
	{
	winner[i][j] = min(winner[i][j - 1], v[j]);
	}
	}
	memset(cache, -1, sizeof(cache));
	cout << func(0, N - 1) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~