백준 15997 승부 예측

https://www.acmicpc.net/problem/15997

15997번: 승부 예측

풀이 

0. 문제를풀기 앞서서 풀어야되는 문제

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

아이디어가 어려운 문제는 아니지만 조합론 정도는 아셔야 이해하기 쉽습니다.

 

1. 핵심 아이디어

 

팀의 4개뿐이므로 진행되는 경기의 수는 6개가된다.

경기마다 승,무승부,패라는 3가지 경우의 수로 나뉘게되고

모든 경우를 고려한다면 3^6=729가지의 경우의 수가 나오게된다.

 

충분히 모두 탐색할만하므로 탐색해서 구하도록한다.

(필자는 DFS를 사용해서 모든 경우를 탐색하도록 구현했다.)

 

---

이 문제에서 주의해야할 점은 승점이 같은경우 확률처리이다.

승점이 같은경우 추첨을 통해서 랜덤하게 다음라운드로 갈 국가를 구하기 때문에

그것을 고려해서 확률을 처리해야한다.(코드를 참조)

 

 

 

코드

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

const float INF = 1e10;
const int Dic[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

//////////////////////////////////////////////////////////////////////// 

int WinPoint[4] = { 0, };
float Rate[4];
float W[4][4];
float D[4][4];
float L[4][4];

map<string, int> Idx;
vector<pair<int, int>> battle;

void DFS(int d, float per)
{
	if (per == 0)
		return;

	if (d < 6)
	{
		int idxA = battle[d].first;
		int idxB = battle[d].second;

		WinPoint[idxA] += 3;
		DFS(d + 1, per * W[idxA][idxB]);
		WinPoint[idxA] -= 3;

		WinPoint[idxA] += 1;
		WinPoint[idxB] += 1;
		DFS(d + 1, per * D[idxA][idxB]);
		WinPoint[idxA] -= 1;
		WinPoint[idxB] -= 1;

		WinPoint[idxB] += 3;
		DFS(d + 1, per * L[idxA][idxB]);
		WinPoint[idxB] -= 3;
	}
	else
	{
		vector<pair<int, int>> Arr;
		for (int i = 0; i < 4; i++)
			Arr.emplace_back(-WinPoint[i], i);

		sort(Arr.begin(), Arr.end());

		int maxPoint = 0;
		int maxIdxLen = 0;
		vector<int> maxIdx;

		{
			//가장 높은 점수를 가진 사람들을 구한다.
			maxPoint = Arr[0].first;
			maxIdxLen = maxIdx.size();
			for (int i = 0; i < 4; i++)
				if (Arr[i].first == maxPoint)
					maxIdx.push_back(Arr[i].second);
		}


		//승점처리

		if (maxIdxLen == 1)
		{
			//가장 높은 점수를 가진사람이 1명
			Rate[maxIdx[0]] += per;

			{
				//두번째로 높은 점수를 가진 사람들을 구한다.
				maxIdx.clear();
				maxPoint = Arr[1].first;
				for (int i = 1; i < 4; i++)
					if (Arr[i].first == maxPoint)
						maxIdx.push_back(Arr[i].second);
			}

			//두번째로 높은 점수를 가진사람중 1명을 랜덤으로 뽑을 확률을 처리한다.
			maxIdxLen = maxIdx.size();
			for (int i = 0; i < maxIdxLen; i++)
			{
				float v = per / (float)maxIdxLen;
				Rate[maxIdx[i]] += v;
			}
		}
		else if (maxIdxLen == 2)
		{
			//가장 높은 점수를 가진사람이 2명
			//2명중 2명을 뽑을 확률을 고려해서 배분
			Rate[maxIdx[0]] += per;
			Rate[maxIdx[1]] += per;
		}
		else if (maxIdxLen == 3)
		{
			//가장 높은 점수를 가진사람이 3명
			//3명중 2명을 뽑을 확률을 고려해서 배분
			Rate[maxIdx[0]] += (per * 2) / (float)3;
			Rate[maxIdx[1]] += (per * 2) / (float)3;
			Rate[maxIdx[2]] += (per * 2) / (float)3;
		}
		else if (maxIdxLen == 4)
		{
			//가장 높은 점수를 가진사람이 4명
			//4명중 2명을 뽑을 확률을 고려해서 배분
			Rate[maxIdx[0]] += per / (float)2;
			Rate[maxIdx[1]] += per / (float)2;
			Rate[maxIdx[2]] += per / (float)2;
			Rate[maxIdx[3]] += per / (float)2;
		}
	}
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

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

	for (int i = 0; i < 4; i++)
	{
		string s;
		std::cin >> s;
		Idx[s] = i;
	}

	for (int i = 0; i < 6; i++)
	{
		string a, b;
		std::cin >> a >> b;
		int idxA = Idx[a];
		int idxB = Idx[b];
		battle.emplace_back(idxA, idxB);

		std::cin >> W[idxA][idxB] >> D[idxA][idxB] >> L[idxA][idxB];
		W[idxA][idxB] *= 1000;
		D[idxA][idxB] *= 1000;
		L[idxA][idxB] *= 1000;
	}

	DFS(0, 1);

	for (int i = 0; i < 4; i++)
		std::cout << Rate[i] / (float)1000000000000000000 << endl;
}