[BOJ] 1404 - 토너먼트 승자

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

BOJ - 토너먼트 승자

문제 유형: 확률론, 브루트 포스, 구현

문제 난이도: Silver II

시간 제한: 2초

메모리 제한: 128MB

 

문제

최백준은 8명이 참가하는 스타크래프트 토너먼트를 개최했다. 토너먼트는 3개의 라운드로 열리고, 다음과 같이 진행된다.

라운드 1에서 i번 경기는 2×i번 참가자와 2×i+1번 참가자의 경기이다. (0 ≤ i ≤ 3), 4명의 승자가 라운드 2로 진출한다.

라운드 2에서 2*i번 경기의 승자와 2×i+1번 경기의 승자가 서로 경기를 한다. (0 ≤ i ≤ 1), 2명의 승자가 라운드 3에 진출한다.

라운드 2의 승자가 토너먼트의 승자를 가리기 위해서 한 게임을 한다.

8명의 참가자가 서로와 싸웠을 때 이길 수 있는 승률이 주어진다. 이때, 각 참가자가 우승할 수 있는 확률을 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 수 28개가 주어진다. 처음 7개의 수는 0번 참가자가 1번 참가자와 싸워서 이길 수 있는 확률부터 7번 참가자와 싸워서 이길 수 있는 확률이다. 다음 6개의 수는 1번 참가자와 2번 참가자와 싸워서 이길 수 있는 확률부터 7번 참가자와 싸워서 이길 수 있는 확률이다. 이와 같이 주어진다. 모든 수는 정수이다.

 

 

출력

첫째 줄에 각 참가자가 우승할 수 있는 확률을 출력한다. 절대/상대 오차는 10-9까지 허용한다.

 

풀이

4강에 오를 확률은 상대방에 대한 승률이다.

 

결승에 오를 확률은 (자신이 4강에 오를 확률) * (상대방을 이길 확률)인데, 상대방을 이길 확률은 경우의 수를 나눠서 각 상대방이 올라올 확률과 그 상대방을 이길 확률의 합이다.

 

우승 확률은 (자신이 결승에 오를 확률) * (상대방을 이길 확률)이다. 상대방을 이길 확률은 결승에 오를 확률을 구하듯이 각 상대방별 케이스를 구해야 한다.

 

부동소수점 출력에 유의해서 출력한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int winProb[8][8];

int main(int argc, char *argv[]) {
  for (int i = 0; i < 7; ++i) {
    for (int j = i + 1; j <= 7; ++j) {
      cin >> winProb[i][j];
      winProb[j][i] = 100 - winProb[i][j];
    }
  }

  vector<double> quarterProb(8, 1.0);

  for (int i = 0; i < 8; i += 2) {
    quarterProb[i] = quarterProb[i] * winProb[i][i + 1] / 100;
    quarterProb[i + 1] = quarterProb[i + 1] * winProb[i + 1][i] / 100;
  }

  vector<double> finalProb(8);
  for (int i = 0; i < 8; i += 4) {
    finalProb[i] = quarterProb[i] *
                   (quarterProb[i + 2] * winProb[i][i + 2] +
                    quarterProb[i + 3] * winProb[i][i + 3]) /
                   100;
    finalProb[i + 1] = quarterProb[i + 1] *
                       (quarterProb[i + 2] * winProb[i + 1][i + 2] +
                        quarterProb[i + 3] * winProb[i + 1][i + 3]) /
                       100;
    finalProb[i + 2] = quarterProb[i + 2] *
                       (quarterProb[i] * winProb[i + 2][i] +
                        quarterProb[i + 1] * winProb[i + 2][i + 1]) /
                       100;
    finalProb[i + 3] = quarterProb[i + 3] *
                       (quarterProb[i] * winProb[i + 3][i] +
                        quarterProb[i + 1] * winProb[i + 3][i + 1]) /
                       100;
  }

  vector<double> winnerProb(8);

  for (int i = 0; i < 4; ++i) {
    winnerProb[i] =
        finalProb[i] *
        (finalProb[4] * winProb[i][4] + finalProb[5] * winProb[i][5] +
         finalProb[6] * winProb[i][6] + finalProb[7] * winProb[i][7]) /
        100;
  }

  for (int i = 4; i < 8; ++i) {
    winnerProb[i] =
        finalProb[i] *
        (finalProb[0] * winProb[i][0] + finalProb[1] * winProb[i][1] +
         finalProb[2] * winProb[i][2] + finalProb[3] * winProb[i][3]) /
        100;
  }

  cout << fixed << setprecision(9);
  for (int i = 0; i < 8; ++i) {
    cout << winnerProb[i] << " ";
  }
  cout << "\n";

  return 0;
}