백준 15997 (승부예측)

문제

---

심심했던 무지와 콘은 TV를 보다가, 대한민국 선수단이 실시간으로 출전하고 있는 경기를 보게 되었다.

지금 보고 있는 경기는 조별리그가 진행 중인데, 대한민국이 속한 조는 총 4개 국가가 참가하여 경기가 진행되고 있다.

조별리그의 규칙은 다음과 같다.

• 4개의 팀이 조별리그를 진행한다.
• 한 팀은 자신을 제외한 모든 상대방과 한 번씩, 총 3번의 경기를 치른다.
• 경기의 승자는 승점 3점을 받고 비기는 경우 서로 승점 1점을 받는다. 지는 경우에는 승점을 받지 않는다.
• 조별리그를 모두 치른 후 승점 순으로 순위를 정하는데 승점이 같을 시에는 추첨으로 순위를 정하며, 추첨은 공평하게 진행된다. 순위를 정한 후 상위 2팀은 다음 라운드로 진출한다.

전문가들은 조별 리그의 6경기 전체에 대해서 어떤 팀이 승리할 확률, 비길 확률, 패배할 확률을 예측하였다. 무지와 콘은 모든 경기가 독립적으로 진행되었을 때 (어떠한 경기의 결과가 다른 경기의 결과에 영향을 주지 않음), 전문가들의 예상대로 진행된다면 각 팀이 조별리그를 통과하여 다음 라운드로 진출할 확률이 궁금해졌다. 하지만 무지와 콘은 직접 확률을 계산하지 못했고, 여러분들에게 도움을 요청하였다. 무지와 콘을 도와 이 문제를 해결해보자!

 

 

 

 

 

 

풀이

---

깊이우선탐색 방식을 이용하여 완전탐색을 하면 된다.

A팀과 B팀이 경기한다고 했을때

 

A가 이길경우

A와 B가 비길경우

B가 이길경우

 

세가지 경우로 나누어 확률을 구한 뒤 최종 승점에서 순위에 따라 확률을 더해주면 된다.

 

주의할점은 공동 순위일 경우다.

 

공동 1등

공동 1등의 경우는  확률 * 2 / 1등 팀의 수 를 해준 뒤 더해준다.

이경우 2등은 다음 라운드로 진출하지 못한다.

 

공동 2등 

공동 2등의 경우는 확률 / 2등 팀의 수 를 해준뒤 더해준다.

 

이렇게 구현해 주면 된다.

<전체 코드>

import java.io.*;
import java.util.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	static class percent{
		
		int a; 
		int b;
		double win, lose, draw;
		
		public percent(int a, int b, double win, double draw, double lose) {
			this.a = a;
			this.b = b;
			this.win = win;
			this.draw = draw;
			this.lose = lose;
		}
	}
	
	static String[] team;
	static double[] result_Percentage;
	static percent[] game;
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		team = new String[4];
		result_Percentage = new double[4];
		game = new percent[6];
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		for(int i = 0 ; i < 4 ; i++) {
			team[i] = st.nextToken();
		}
		
		for(int i = 0 ; i < 6 ;i++) {
			st = new StringTokenizer(bufferedReader.readLine());
			
			int a = findIndex(st.nextToken());
			int b = findIndex(st.nextToken());
			
			double win = Double.parseDouble(st.nextToken());
			double draw = Double.parseDouble(st.nextToken());
			double lose = Double.parseDouble(st.nextToken());
			
			game[i] = new percent(a, b, win, draw, lose);
		}
				
		int[] score = new int[4];
		playGame(0, 1, score);
		
		
		for(int i = 0 ; i < 4 ; i++) {
			System.out.println(result_Percentage[i]);
		}
	}
	
	static int findIndex(String teamName) {
		for(int i = 0 ; i < 4 ; i++) {
			
			if(team[i].equals(teamName))
				return i;
		}
		
		return -1;
	}
	
	static void playGame(int index, double percent, int[] score) {
		
		if(percent == 0) {
			return;
		}
		
		if(index == 6) {
			int[] rank = new int[4];
			for(int i = 0 ; i < 4;  i++) {
				for(int j = 0 ; j < 4 ; j++) {
					if(i == j)
						continue;
					
					if(score[i] < score[j])
						rank[i]++;
				}
			}
	
			for(int j = 0; j < 2 ; j++) {
				List<Integer> list = new ArrayList<Integer>();
				for(int i = 0 ; i < 4 ; i++) {
					if(rank[i] == j) {
						list.add(i);
					}
				}
				
				if(list.size() >= 2) {
					if( j == 0 ) {
						for(int i = 0 ; i < list.size(); i++) {
							result_Percentage[list.get(i)] += (percent * 2.0 / (double)list.size());
						}
						
						break;
					}
					
					if (j == 1) {
						for(int i = 0 ; i < list.size(); i++) {
							result_Percentage[list.get(i)] += (percent/ (double) list.size());
						}
					}
				}
				else if(list.size() == 1){
					result_Percentage[list.get(0)] += percent;
				}
			}
			
			
			return;
		}
		
		percent g = game[index];
		
		score[g.a] += 3;
		playGame(index + 1 , percent * g.win, score);
		score[g.a] -= 3;
		
		score[g.a]+= 1;
		score[g.b]+= 1;
		playGame(index + 1, percent * g.draw, score);
		score[g.a] -= 1;
		score[g.b] -= 1;
		
		score[g.b] += 3;
		playGame(index + 1 , percent * g.lose, score);
		score[g.b]-= 3; 
		
	}
}