백준 15997. 승부 예측

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

15997번: 승부 예측

 

이 문제는 다음 두가지를 구해야 한다.

 

1. 총 여섯 경기가 진행 되고 각 경기들은 특정 팀이 이기거나, 비기거나, 지는 경우가 있다.

따라서 모든 경우를 다 따져보면 3^6 = 729 경우가 있다. 

해당 경기가 일어날 확률을 구해야한다. 

 

2. 여섯 경기가 진행 된 이후에 각 팀들의 승점들이 있을 것이다. 

해당 승점에 따라 각 팀들이 다음 스테이지로 진출할수 있는 확률을 구해야 한다. 

 

---

우선 1번을 구하는 방법은 dfs로 모든 경우를 탐색하면 된다. 

team1	team2	team1 이기는 확률	비기는 확률	team2 이기는 확률
KOREA	CCC	1.0	0.0	0.0
AAA	BBB	0.428	0.144	0.428
AAA	KOREA	0.0	0.0	1.0
CCC	BBB	0.0	0.0	1.0
KOREA	BBB	1.0	0.0	0.0
CCC	AAA	0.0	0.0	1.0

여기서 첫번째 경우를 생각해보자. 

첫번째 경우는 여섯경기 모두에서 team1이 이기는 경우다.

확률은 모두 곱해주면 된다 즉 여섯 경기에서 모두 team1이 이기는 경우는 = 1.0 * 0.428 * 0.0 * 0.0 * 1.0 * 0.0 이다.

그런데 보다시피 한 경기라도 일어날 확률이 0이라면 0이 곱해져 해당 경기 세트 (여섯 경기를 세트라고 한다면)는 일어날 확률이 0이 되기때문에 더이상 진행할 필요가 없다. 

 

다음 경우는 team1이 이기고, team1이 이기고, team1이 이기고, team1이 이기고, team1이 이기고, 비기는 경우다.

 

이렇게 dfs로 모든 경기 세트들이 일어날 확률을 구할수 있을 것이다.

 

 

 

하나의 경기 세트가 일어날 확률을 구했다면, 각 팀들의 승점에 따라 어느 팀이 다음 라운드로 진출할수 있는지를 판단해야 한다.

다음 네가지 경우를 생각해 봐야 한다. 

 

4개의 팀이 모두 점수가 같은 경우

1,2,3등이 점수가 같은 경우 

2,3,4등이 점수가 같은 경우 

2,3등이 점수가 같은 경우 

 

나머지 경우, 예를들어 1,2등이 점수가 같은 경우는? 어처피 1,2등 모두 진출할 것이기 때문에, 해당 팀이 진출할 확률에 해당 경기가 발생할 확률 을 더해주면 된다.

 

위 4개의 예외적인 상황에서는 따로 계산해줘야 한다.

예를들어 4개의 팀이 모두 점수가 같다면 4개의 팀중 2개의 팀이 진출하기 때문에 해당 경기가 발생할 확률 * (2/4) 를 더해주면 된다.