[BOJ 15997] 승부 예측

풀이

총 경기는 6경기이고 각 경기당 나올 수 있는 결과는 W D L 3가지 이기 때문에 3^6개의 경우의 수가 나온다.

모든 경우를 순회하면서 확률을 계산하고 계산된 확률의 결과를 처리해주면 되는 문제이다.

6경기가 끝난 후 나올 수 있는 결과는

1등이 확실한 경우

• (2 != 3)

2팀이 동점인 경우

• (2 == 3) -> (2,3등이 1/2 확률)

3팀이 동점인 경우

• (1 == 2 == 3 > 4) -> (1,2,3등이 2/3확률)
• (1 > 2 == 3 == 4) -> (2,3,4등이 1/3확률)

4팀이 동점인 경우

• (1 == 2 == 3 == 4) -> (1,2,3,4등이 1/2확률)

dfs로 모든 경우를 계산해주면 답을 찾을 수 있다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

struct info {
	int x, y;
	double win, draw, lose;
};

map<string, int> m;
info arr[6];
int score[4];
double winRate[4];


void dfs(int d, double p) {

	if (d == 6) {
		pair<int, int>temp[4];
		for (int i = 0; i < 4; i++) {
			temp[i].first = score[i];
			temp[i].second = i;
		}
		sort(temp, temp + 4);
		if (temp[1].first != temp[2].first) { // 1,2등이 확실할 경우
			winRate[temp[2].second] += p;
			winRate[temp[3].second] += p;
		}
		else if (temp[0].first == temp[1].first && temp[1].first == temp[2].first && temp[2].first == temp[3].first) { //0 == 1==2==3
			winRate[temp[0].second] += p * (1 / 2.0); winRate[temp[1].second] += p * (1 / 2.0);
			winRate[temp[2].second] += p * (1 / 2.0); winRate[temp[3].second] += p * (1 / 2.0);
		}
		else if (temp[1].first == temp[2].first && temp[2].first == temp[3].first) { // 0 < 1 == 2 == 3
			winRate[temp[1].second] += p * (2 / 3.0); winRate[temp[2].second] += p * (2 / 3.0); winRate[temp[3].second] += p * (2 / 3.0);
		}
		else if (temp[0].first == temp[1].first && temp[1].first == temp[2].first) { // 0 == 1 == 2 < 3
			winRate[temp[3].second] += p; winRate[temp[0].second] += p * (1 / 3.0); winRate[temp[1].second] += p * (1 / 3.0); winRate[temp[2].second] += p * (1 / 3.0);
		}
		else if (temp[1].first == temp[2].first) { // 0 < 1 == 2 < 3
			winRate[temp[3].second] += p; winRate[temp[1].second] += p * (1 / 2.0); winRate[temp[2].second] += p * (1 /  2.0);
		}
		return;
	}

	int x = arr[d].x, y = arr[d].y;
	score[x] += 3;
	dfs(d + 1, p * arr[d].win);
	score[x] -= 3;

	score[x] += 1; score[y] += 1;
	dfs(d + 1, p * arr[d].draw);
	score[x] -= 1; score[y] -= 1;

	score[y] += 3;
	dfs(d + 1, p * arr[d].lose);
	score[y] -= 3;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	for (int i = 0; i < 4; i++) {
		string country;
		cin >> country;
		m[country] = i;
	}

	int score[4] = { 0,0,0,0 };
	for (int i = 0; i < 6; i++) {
		string a, b;
		float w, d, l;
		cin >> a >> b >> w >> d >> l;
		arr[i] = { m[a], m[b], w,d,l };
	}

	dfs(0, 1.0);

	for (auto x : winRate) cout << x << '\n';


	return 0;
}