어흥
[백준 15997] 승부 예측 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/15997
1. 주의할 점
- 브루트포스를 통해 구하지만, 3^6 전부를 돌리지 않아도 된다
- 독립 사건 → 확률을 곱하면서 진행
2. 구현
- Map을 통해 각 문자열에 매칭되는 번호를 저장한다
- Matches[idx]를 통해 idx번째 경기에 누가 참가하는지 저장핟나
- WinRate[idx][]를 통해 idx번째 경기의 승무패 확률을 저장한다
- DFS를 수행하여 최대 6번의 경기를 치르도록 한다. 이때, 각 조건이 발생할 확률이 0인것은 Continue를 수행하여 무시한다
- 6번의 경기 결과를 구했다면 Points[] 배열에 각 팀이 얻은 점수를 종합한다
- 우선순위큐를 통해 점수의 내림차순으로 정렬한다
- 인덱스 접근을 위해 Ranking 벡터에 내림차순으로 정리된 우선순위큐의 원소들을 저장한다
- 각 조건에 따라 팀이 올라갈 확률을 계산하여 Percent[]에 저장한다
#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
struct info {
int idx, score;
};
struct cmp {
bool operator()(info &a, info &b) {
return a.score < b.score;
}
};
using namespace std;
double percent[4];
double winRate[6][3];
vector<int> v, matches[6];
int totalMatch = 0;
void dfs(int cnt,double win) {
if(cnt == 6) {
totalMatch++;
int points[4] = { 0, };
for (int i = 0; i < 6; i++) {
int val = v[i];
if (val == 0) points[matches[i][0]] += 3;
else if(val==2) points[matches[i][1]] += 3;
else {
points[matches[i][0]]++;
points[matches[i][1]]++;
}
}
priority_queue<info, vector<info>, cmp> pq;
vector<info> ranking;
for (int i = 0; i < 4; i++)
pq.push({ i,points[i] });
while(!pq.empty()){
int idx = pq.top().idx;
int score = pq.top().score;
pq.pop();
ranking.push_back({idx,score});
}
if(ranking[1].score>ranking[2].score){ //앞 2팀 확정
percent[ranking[0].idx]+=win;
percent[ranking[1].idx]+=win;
}
else if(ranking[0].score==ranking[1].score && ranking[2].score==ranking[3].score){ //1,1,1,1 ->4팀중 2
percent[ranking[0].idx]+=win/2;
percent[ranking[1].idx]+=win/2;
percent[ranking[2].idx]+=win/2;
percent[ranking[3].idx]+=win/2;
}
else if(ranking[2].score==ranking[3].score){ //1,2,2,2 ->3팀중 1
percent[ranking[0].idx]+=win;
percent[ranking[1].idx]+=win/3;
percent[ranking[2].idx]+=win/3;
percent[ranking[3].idx]+=win/3;
}
else if(ranking[0].score==ranking[1].score){ //1,1,1,3 ->3팀중 2
percent[ranking[0].idx]+=(win*2)/3;
percent[ranking[1].idx]+=(win*2)/3;
percent[ranking[2].idx]+=(win*2)/3;
}
else{ //1,2,2,4 ->2팀중 1
percent[ranking[0].idx]+=win;
percent[ranking[1].idx]+=win/2;
percent[ranking[2].idx]+=win/2;
}
return;
}
for (int i = 0; i < 3; i++) {
double val = winRate[cnt][i];
if (val == 0) continue;
v.push_back(i);
dfs(cnt + 1, win*val);
v.pop_back();
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
string str,s;
map<string, int> m;
for (int i = 0; i < 4; i++) {
cin >> str;
m[str] = i;
}
for (int i = 0; i < 6; i++) {
for(int j=0;j<5;j++) {
cin >> str;
if (j < 2) matches[i].push_back(m[str]);
else winRate[i][j - 2] = stod(str);
}
}
dfs(0, 1.0);
cout << fixed;
cout.precision(6);
for (int i = 0; i < 4; i++)
cout << percent[i] << " ";
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 16964] DFS 스페셜 저지 (Java) (0) | 2022.02.16 |
---|---|
[백준 19598] 최소 회의실 개수 (C++) (0) | 2022.02.11 |
[백준 2026] 소풍 (C++, Java) (0) | 2022.01.16 |
[백준 9007] 카누 선수 (C++) (0) | 2022.01.12 |
[백준 3107] IPv6 (C++, Java) (0) | 2022.01.04 |
Comments