[BOJ] 15997 승부 예측

문제 링크

 

www.acmicpc.net/problem/15997

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

오늘은 2018년 카카오 코드 페스티벌에서 출제된 문제를 풀어봤다. 문제를 처음 봤을 때는 어떻게 풀어야 할지 감이 잘 잡히지 않았지만 리그에 참여하는 국가와 경기 수가 4, 6이라는 작은 수로 정해져 있어 모든 경기 결과를 완전탐색하면 문제를 해결할 수 있을 것이라 생각했다. 문제에서 주어진 각 경기에 대한 정보는 구조체를 이용하기로 하고 아래와 같은 구조체를 생성했다.

typedef struct game {
	int x, y;
	double win, draw, lose;
}Game;

x와 y는 참가하는 국가를 입력 순으로 번호를 매겨서 저장하기로 했으며, win, draw, lose에는 각각 x국가가 이길 확률, 비길 확률, 질 확률을 저장하기로 했다. 국가 번호를 매기기 위해 map을 사용했다.

 

문제 해결을 위한 함수는 매개변수로 idx와 proc를 받으며, idx는 처리해야 할 경기 번호, proc는 지금까지의 확률을 나타낸다. 함수에 대한 설명은 주석에 나와있다.

 

void func(int idx, double proc) {
	if (idx == 6) { // 경기 끝나고 확률 더해주기
		if (proc == 0) return;
		for (int i = 0; i < 4; i++) {
			finalScore[i] = {score[i], i};
		}
		sort(finalScore.begin(), finalScore.end());
		int aScore = finalScore[0].first,
			bScore = finalScore[1].first,
			cScore = finalScore[2].first,
			dScore = finalScore[3].first;

		int a = finalScore[0].second,
			b = finalScore[1].second,
			c = finalScore[2].second,
			d = finalScore[3].second;
		/*----------------------------------------------------------------------------------
			점수 경우의 수
			1. b != c-> c, d 진출
			2. b == c -> d 진출, b/c 추첨하여 한 명 진출 -> b와 c는 p/2 확률로 진출
			3. a == b == c -> d 진출, a/b/c 추첨하여 한 명 진출 -> a/b/c는 p/3 확률로 진출
			4. b == c == d -> b/c/d 추첨하여 두 명 진출 -> b/c/d p*2/3 확률로 진출
			5. a == b == c == d -> a/b/c/d 추첨하여 두 명 진출 -> a/b/c/d p/2 확률로 진출
			                                                       
		-----------------------------------------------------------------------------------*/

		if (bScore != cScore) { // 1
			ret[c] += proc;
			ret[d] += proc;
		}
		else if (aScore == bScore && cScore == dScore) { // 5
			ret[a] += proc / 2;
			ret[b] += proc / 2;
			ret[c] += proc / 2;
			ret[d] += proc / 2;
		}
		else if (aScore == bScore) { // 3
			ret[a] += proc / 3;
			ret[b] += proc / 3;
			ret[c] += proc / 3;
			ret[d] += proc;
		}
		else if (cScore == dScore) { // 4
			ret[b] += proc * 2 / 3;
			ret[c] += proc * 2 / 3;
			ret[d] += proc * 2 / 3;
		}
		else { // 2
			ret[b] += proc / 2;
			ret[c] += proc / 2;
			ret[d] += proc;
		}
		return;
	}

	/*-----------------------------------------
		idx번째 게임의 참가자를 x, y라 하자.
		1. x가 이겼을 때
		2. 비겼을 때
		3. y가 이겼을 때
		로 나눌 수 있다. 각각의 경우 완전탐색
	-----------------------------------------*/

	Game g = gameArr[idx];
	//1. x가 이겼을 때
	score[g.x] += 3;
	func(idx + 1, proc * g.win);
	score[g.x] -= 3;

	//2. 둘이 비겼을 때
	score[g.x]++;
	score[g.y]++;
	func(idx + 1, proc * g.draw);
	score[g.x]--;
	score[g.y]--;

	//3. y가 이겼을 때
	score[g.y] += 3;
	func(idx + 1, proc * g.lose);
	score[g.y] -= 3;
}

 

이 함수에는 score, finalScore, gameArr, ret 배열이 사용된다.score는 크기 6의 int 배열이며, 각각의 국가가 얻은 총 점수를 나타낸다. finalScore는 크기 6의 pair<int, int>를 저장하고 있는 벡터이며, 점수순으로 정렬하여 진출할 국가를 확인하기 위해 사용한다. gameArr 배열에는 각 경기 정보를 나타내는 6개의 Game 구조체가 들어있다. 마지막으로 ret배열에는 4개 국가가 다음 라운드로 진출할 최종 확률을 저장한다. 

 

func 함수의 수행이 끝나면 ret 배열에 저장된 4개의 확률을 차례대로 출력해주면 된다. 전체 코드는 아래와 같다.

 

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
map<string, int> mp;

typedef struct game {
	int x, y;
	double win, draw, lose;
}Game;

Game gameArr[6];
double ret[6];
int score[6];
vector<pair<int, int>> finalScore(4);
void func(int idx, double proc) {
	if (idx == 6) { // 경기 끝나고 확률 더해주기
		if (proc == 0) return;
		for (int i = 0; i < 4; i++) {
			finalScore[i] = {score[i], i};
		}
		sort(finalScore.begin(), finalScore.end());
		int aScore = finalScore[0].first,
			bScore = finalScore[1].first,
			cScore = finalScore[2].first,
			dScore = finalScore[3].first;

		int a = finalScore[0].second,
			b = finalScore[1].second,
			c = finalScore[2].second,
			d = finalScore[3].second;
		/*----------------------------------------------------------------------------------
			점수 경우의 수
			1. b != c-> c, d 진출
			2. b == c -> d 진출, b/c 추첨하여 한 명 진출 -> b와 c는 p/2 확률로 진출
			3. a == b == c -> d 진출, a/b/c 추첨하여 한 명 진출 -> a/b/c는 p/3 확률로 진출
			4. b == c == d -> b/c/d 추첨하여 두 명 진출 -> b/c/d p*2/3 확률로 진출
			5. a == b == c == d -> a/b/c/d 추첨하여 두 명 진출 -> a/b/c/d p/2 확률로 진출
			                                                       
		-----------------------------------------------------------------------------------*/

		if (bScore != cScore) { // 1
			ret[c] += proc;
			ret[d] += proc;
		}
		else if (aScore == bScore && cScore == dScore) { // 5
			ret[a] += proc / 2;
			ret[b] += proc / 2;
			ret[c] += proc / 2;
			ret[d] += proc / 2;
		}
		else if (aScore == bScore) { // 3
			ret[a] += proc / 3;
			ret[b] += proc / 3;
			ret[c] += proc / 3;
			ret[d] += proc;
		}
		else if (cScore == dScore) { // 4
			ret[b] += proc * 2 / 3;
			ret[c] += proc * 2 / 3;
			ret[d] += proc * 2 / 3;
		}
		else { // 2
			ret[b] += proc / 2;
			ret[c] += proc / 2;
			ret[d] += proc;
		}
		return;
	}

	/*-----------------------------------------
		idx번째 게임의 참가자를 x, y라 하자.
		1. x가 이겼을 때
		2. 비겼을 때
		3. y가 이겼을 때
		로 나눌 수 있다. 각각의 경우 완전탐색
	-----------------------------------------*/

	Game g = gameArr[idx];
	//1. x가 이겼을 때
	score[g.x] += 3;
	func(idx + 1, proc * g.win);
	score[g.x] -= 3;

	//2. 둘이 비겼을 때
	score[g.x]++;
	score[g.y]++;
	func(idx + 1, proc * g.draw);
	score[g.x]--;
	score[g.y]--;

	//3. y가 이겼을 때
	score[g.y] += 3;
	func(idx + 1, proc * g.lose);
	score[g.y] -= 3;
}
int main() {
	int i;
	string a, b;
	double p, q, r;
	for (i = 0; i < 4; i++) {
		cin >> a;
		mp[a] = i;
	}

	for (i = 0; i < 6; i++) {
		cin >> a >> b >> p >> q >> r;
		gameArr[i] = { mp[a], mp[b], p, q, r };
	}

	func(0, 1.0);

	cout << fixed;
	cout.precision(10);
	for (i = 0; i < 4; i++) {
		cout << ret[i] << endl;
	}
}