백준 15997 - 승부 예측

백준 승부예측

15997번: 승부 예측

---

승부 예측 문제는 각 4팀이 다음 라운드로 진출할 확률이 얼마나 되는지 구하는 문제다.

처음에 봤을 때 막막했지만, 침착하게 생각하니 풀 수 있었다.

먼저 이 문제의 핵심은 다음과 같다.

위 그림처럼 모든 경우의 수에 대해 탐색을 해봐야 한다.(선은 다 그리진 못 했다.)

총 6경기를 하는데 각 6경기마다 이기고 비기고 지는 3가지 경우가 생기기때문에

모든 경우의 수는 3의 6승 = 729가 된다.

하지만 확률 중 0이 있으면 경우의 수는 줄어든다.

이기고 비기고 지는 3가지 경우 중 발생할 확률이 0인 경우가 있다면
해당 경기에서 발생하는 경우의 수는 2가지 혹은 1가지 경우로 줄기때문이다.
ex) 이길 확률이 0이라면 비기고 지는 2가지 경우만 발생한다

 

1단계: 확률 구하기

탐색을 하면서 해당 경우의 수가 발생하는 확률을 함께 구해야 한다.

이 때 확률이 0%인 경우는 탐색을 이어나갈 필요가 없다. 

위와 같은 입력이 있을 때 DDD가 이기고 다음 경기에서 AAA가 이길 확률은 몇 %일까?

0.5 * 0.5 = 0.25 = 25%이다.

더 쉽게 말하면 50%(1/2)가 두 번 일어날 확률은 50% * 50%(1/2 * 1/2) = 25%가 된다.

즉 어떤 일이 연달아 일어나는지 계산하려면 곱해보면 된다는 것이다.
따라서 탐색 시 발생확률을 계산하기 위해 이전 확률에 현재 경기결과가 일어날 확률을 곱해주면 된다.
그러면 6경기가 끝났을 때 최종적으로 해당 6경기 결과에 대한 확률이 나오게 된다.

percent = percent * rate[y][x];

// win, draw, lose를 탐색하기 위한 for
for(int j = 0; j < 3; j++) dfs(y + 1, j, percent, score.clone());

 

2단계: 승점 구하기

각 경기 결과에 대해 국가에 알맞게 승점을 누적시켜줘야 한다.

if(x == 0) score[nationIndex.get(twoNations[y][0])] += 3;
else if(x == 1) {
  score[nationIndex.get(twoNations[y][0])] += 1;
  score[nationIndex.get(twoNations[y][1])] += 1;
} else score[nationIndex.get(twoNations[y][1])] += 3;
percent = percent * rate[y][x];

// win, draw, lose를 탐색하기 위한 for
for(int j = 0; j < 3; j++) dfs(y + 1, j, percent, score.clone());

 

3단계: 각 라운드 진출 확률 구하기

위 2단계를 거치면 어떤 확률로 어떤 승점 결과가 나오게 되는지 알아낼 수 있다.

1~2단계를 거쳐 다음과 같이 결과가 나왔다고 하자!
50% 확률로 AAA: 진출, BBB: 진출, CCC: 미진출, DDD: 미진출
30% 확률로 AAA: 미진출, BBB: 진출, CCC: 진출, DDD: 미진출

20% 확률로 AAA: 진출, BBB: 미진출, CCC: 진출, DDD: 미진출

 

그러면 최종적으로 각 팀의 진출 확률은 다음과 같다.

AAA: 70%, BBB: 80%, CCC: 50%, DDD: 0%

즉,  최종확률에서 자신이 진출하는 확률들을 가산해주면 된다.

 

이 때 주의할 점은 공동 1등과 공동 2등이다.

2단계를 통해서 나온 결과의 확률을 x라고 하면 
공동 1등의 확률은 다음과 같다.

참고로 1등이 2팀 이상이 되면 2등은 다음 라운드에 진출이 불가능하다

공동1등(팀)	1등의 다음 라운드 진출 확률	설명
4	x * 2/4	4팀 중 2팀이 진출하므로 x(해당 경기가 일어날 확률)에 2/4를 곱해준다.
3	x * 2/3	3팀 중 2팀이 진출하므로 x(해당 경기가 일어날 확률)에 2/3를 곱해준다.
2	x * 2/2	2팀 중 2팀이 진출하므로 x(해당 경기가 일어날 확률)에 2/2를 곱해준다. 즉, 해당 경기가 일어나면 반드시 진출한다. = x% 확률로 진출
1	x *  1	해당 경기가 일어나면 반드시 진출한다. 즉 x% 확률로 진출

2등은 1등이 1팀인 경우에 한해서 1팀만 진출 가능하다.

따라서 수식은 다음과 같다.

x(해당 경기가 일어날 확률) * 1 / 공동 2등팀 개수 = x / 공동 2등팀 개수

'1 / 공동 2등팀 개수'는 공동 2등팀 개수 중에 1팀만 진출한다는 뜻으로 풀어서 써놓은 것이다.

 

int sorted[] = score.clone(), first = 0, second = 0;
Arrays.sort(sorted);
for(int i = 0; i < 4; i++) {
  if(sorted[3] == sorted[i]) first++;
  if(sorted[2] == sorted[i]) second++;
}
double firstRate = 1;
if(first >= 2) firstRate = 2.0 / first;

for(int i = 0; i < 4; i++) {
  if (sorted[3] == score[i]) answer[i] = percent * firstRate + answer[i];
  if (first == 1) if(sorted[2] == score[i]) answer[i] = percent / second + answer[i];
}
return;

---

최종 코드

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

public class Main {

    static double rate[][] = new double[6][3];
    static String twoNations[][] = new String[6][2];
    static HashMap<String, Integer> nationIndex = new HashMap<>();
    static double answer[] = new double[4];

    // 백준 15997 - 승부 예측
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer nations = new StringTokenizer(bufferedReader.readLine());
        for(int i = 0; i < 4; i++) {
            nationIndex.put(nations.nextToken(), i);
            answer[i] = 0;
        }

        for(int i = 0; i < 6; i++) {
            StringTokenizer data = new StringTokenizer(bufferedReader.readLine());
            for(int j = 0; j< 2; j++) twoNations[i][j] = data.nextToken();
            for(int j = 0; j < 3; j++) rate[i][j] = strToDouble(data.nextToken());
        }

        int score[] = new int[4];
        for(int j = 0; j < 3; j++) {
            dfs(0, j, 1, score.clone());
        }

        for(int i = 0; i < 4; i++) System.out.println(answer[i]);
    }

    // y좌표, x좌표, 확률, 4팀의 점수
    static void dfs(int y, int x, double percent, int score[]) {
        // 확률이 0%인 경우 return
        if(rate[y][x] == 0) return;

        if(x == 0) score[nationIndex.get(twoNations[y][0])] += 3;
        else if(x == 1) {
            score[nationIndex.get(twoNations[y][0])] += 1;
            score[nationIndex.get(twoNations[y][1])] += 1;
        } else score[nationIndex.get(twoNations[y][1])] += 3;
        percent = percent * rate[y][x];

        if(y == 5) {
            int sorted[] = score.clone(), first = 0, second = 0;
            Arrays.sort(sorted);
            for(int i = 0; i < 4; i++) {
                if(sorted[3] == sorted[i]) first++;
                if(sorted[2] == sorted[i]) second++;
            }
            double firstRate = 1;
            if(first >= 2) firstRate = 2.0 / first;

            for(int i = 0; i < 4; i++) {
                if (sorted[3] == score[i]) answer[i] = percent * firstRate + answer[i];
                if (first == 1) if(sorted[2] == score[i]) answer[i] = percent / second + answer[i];
            }
            return;
        }

        // win, draw, lose를 탐색하기 위한 for
        for(int j = 0; j < 3; j++) dfs(y + 1, j, percent, score.clone());
    }

    private static double strToDouble(String str) {
        return Double.parseDouble(str);
    }
}