[백준/BOJ] 백준 15997번 : 승부 예측

www.acmicpc.net/problem/15997

15997번: 승부 예측

각 경기의 상황(승리, 무승부, 패배)을 모두 고려해서, 모든 경기를 고려했을 때 그때 다음 라운드에 진출할 수 있는 팀들의 확률을 계산해서 문제를 해결한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>
#include <string>
#include <map>
using namespace std;

map<string, int> world_number;
vector<double> result(4, 0);
struct wdl {
	double win;
	double draw;
	double lose;
};
vector<pair<pair<int, int>, wdl>> match_info;

void Match(vector<int>& score, double rate, int index)
{
	//모든 경기를 다 확인 했을때
	if (index == 6)
	{
		vector<pair<int, int>> sort_vector;

		for (int i = 0; i < 4; i++)
			sort_vector.push_back(make_pair(score[i], i));

		sort(sort_vector.begin(), sort_vector.end());
		reverse(sort_vector.begin(), sort_vector.end()); //내림차순으로 정렬된다

		vector<int> rank[4]; //각 순위에 해당하는 팀들을 저장한다
		double here_score = 987654321.0;
		int here_rank = 0;
		for (int i = 0; i < sort_vector.size(); i++)
		{
			if (here_score > sort_vector[i].first)
			{
				rank[here_rank].push_back(sort_vector[i].second);

				here_score = sort_vector[i].first;
				here_rank++;
			}

			//앞의 점수와 점수가 같을때 (같은 순위일때)
			else if (here_score == sort_vector[i].first)
			{
				rank[here_rank - 1].push_back(sort_vector[i].second);
			}

		}

		int select_num = 0;

		for (int i = 0; i < 4; i++)
		{
			int before_select_num = select_num;
			select_num += rank[i].size();

			if (select_num > 2)
			{
				for (int j = 0; j < rank[i].size(); j++)
				{
					result[rank[i][j]] += ((rate) * ((double)(2 - before_select_num) / rank[i].size()));
				}
			}

			else
			{
				for (int j = 0; j < rank[i].size(); j++)
				{
					result[rank[i][j]] += rate;
				}
			}

			if (select_num >= 2)
				break;
		}

		return;
	}

	int world1 = match_info[index].first.first;
	int world2 = match_info[index].first.second;

	//world1이 이길때
	score[world1] += 3;
	Match(score, rate * match_info[index].second.win, index + 1);
	score[world1] -= 3;

	//비길때
	score[world1] += 1;
	score[world2] += 1;
	Match(score, rate * match_info[index].second.draw, index + 1);
	score[world1] -= 1;
	score[world2] -= 1;

	//world2가 이길때
	score[world2] += 3;
	Match(score, rate * match_info[index].second.lose, index + 1);
	score[world2] -= 3;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	for (int i = 0; i < 4; i++)
	{
		string input;
		cin >> input;

		world_number.insert(make_pair(input, i));
	}

	for (int i = 0; i < 6; i++)
	{
		string a, b;
		double w, d, l;
		wdl this_wdl;

		cin >> a >> b >> w >> d >> l;

		int a_number = world_number[a];
		int b_number = world_number[b];
		this_wdl = { w,d,l };

		match_info.push_back(make_pair(make_pair(a_number, b_number), this_wdl));
	}

	vector<int> score(4, 0);

	Match(score, 1, 0);

	cout << fixed;
	cout.precision(10);

	for (int i = 0; i < 4; i++)
		cout << result[i] << "\n";

	return 0;
}