# 브루트 포스 # 완탐 # 카카오 코드 페스티벌
전체 시간복잡도가 3^6이여서 완탐으로 탐색하면된다.
다만 중복된 검사부분이 상당히 귀찮다.
#include <iostream> #include <vector> #include <queue> #include <algorithm> #include <string.h> using namespace std; #define pi pair<int,int> bool cmp(pi a, pi b) { return a.first > b.first; } // 비교 함수 struct st { // is는 현재 이기고, 무승부, 진것에 대한 offset int a[2]; double b[3]; int is; }; char str[4][15], input[15]; double ans[4]; st v[10]; void dfs(int sz) { if (sz == 6) { // 각 국의 승점 및 확률 계산 int s[4] = { 0, }; double ret = 1; for (int i = 0; i < 6; i++) { int cur = v[i].is; ret *= v[i].b[cur]; if (cur == 0) s[v[i].a[0]] += 3; else if (cur == 2) s[v[i].a[1]] += 3; else { s[v[i].a[0]] += 1; s[v[i].a[1]] += 1; } } // 동점자 계산 및 각 국에 확률 더해주기 vector<pi> vp; for (int i = 0; i < 4; i++) vp.push_back({ s[i],i }); int cnt = 2; while (cnt > 0) { int num = 0, mx; sort(vp.begin(), vp.end(), cmp); mx = vp.front().first; for (int i = 0; i < 4; i++) if (vp[i].first == mx) num++; for (int i = 0; i < num; i++) { double add = cnt > num ? ret : ret * ((float)cnt / num); ans[vp[i].second] += add; vp[i].first = -1; } cnt -= cnt > num ? num : cnt; } return; } // 완탐 검색 for (int i = 0; i < 3; i++) { v[sz].is = i; dfs(sz + 1); } } int main() { for (int i = 0; i < 4; i++) scanf("%s", str[i]); for (int i = 0; i < 6; i++) { for (int j = 0; j < 2; j++) { scanf("%s", input); for (int p = 0; p < 4; p++) if (strcmp(str[p], input) == 0) v[i].a[j] = p; } for (int j = 0; j < 3; j++) scanf("%lf", &v[i].b[j]); } dfs(0); for (int i = 0; i < 4; i++) printf("%.10lf\n", ans[i]); return 0; }
'IT > BOJ' 카테고리의 다른 글
백준(BOJ) 15684 치킨 배달 * (0) | 2019.04.02 |
---|---|
백준(BOJ) 15684 사다리 조작 ** (0) | 2019.03.28 |
백준(BOJ) 15683 감시 * (0) | 2019.03.26 |
백준(BOJ) 14891 톱니바퀴 * (0) | 2019.03.25 |
백준(BOJ) 14890 경사로 ** (0) | 2019.03.22 |