[백준] 승부예측 (파이썬)

문제링크

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

15997번: 승부 예측

 

문제풀이

이 문제는 해결 방법을 떠올리기도 어렵고, 구현하는게 복잡한 문제이다.

총 4개의 팀이 6번의 매치를 하는데 각 매치마다 이기거나, 지거나, 비기는 모든 경우의 확률을

완전탐색한 뒤 1등과 2등을 뽑아 1등과 2등에게 각각의 확률을 더해주는 식으로 문제를 풀면된다.

 

이 문제를 구현하기 까다로웠는데 그 이유는,

1. 재귀함수와 for 문, 스택을 이용한 완전탐색 구현 

2. 데이터 파싱

3. 공동 1,2 등이 나올 각각의 케이스 분류

였다.

 

모든 매치는 총 3가지 경우의 수가 존재한다.( Win, Lose, Draw )

chance 라는 배열은 각 매치의 결과를 담은 배열이다.

만약 chance 의 길이가 6 일경우, 모든 매치가 종료된 것이므로 이때 1,2 등을 구해 확률을 더해주면 된다.

또한 for 문 밖에 chance.pop() 을 만들어줘서 재귀가 정상적으로 돌아가도록 만들어주었다.

 

시간복잡도

기본적으로 3^6 의 모든 경우의 수를 탐색하는데, 

각 경우마다 k번 의 예외처리를 해주어야 하므로,

TC = 3^6 * k 즉, Big(O) = (3^n) 이다.

 

소스코드

from collections import defaultdict;

teams = list(input().split());
chances = [];
ans = defaultdict(list);

for team in teams:
    ans[team] = 0;

for i in range(6):
    temp = list(input().split());
    chances.append(temp);

def calChance(chance, ans):
    mm = 1.00000000;
    d = defaultdict(int);

    for c in chance:
        teamA = c[0];
        scoreA = int(c[1]);
        teamB = c[2];
        scoreB = int(c[3]);
        m = float(c[4]);
        mm *= m;
        d[teamA] += scoreA;
        d[teamB] += scoreB;
    d = dict(sorted(d.items(), key=lambda item : -item[1]));
    
    temp = [];
    for key in d.keys():
        temp.append([key, d[key]]);
    
    # 2 등이 3등보다 승점이 높은경우
    if (temp[1][1] > temp[2][1]):
        ans[temp[0][0]] += mm;
        ans[temp[1][0]] += mm;
    
    # 2 등이 3등과 점수가 같을 경우
    else:
        # 3,4 등도 2등과 점수가 같은경우
        if (temp[2][1] == temp[3][1]):
            # 1,2 등도 점수가 같은경우
            if (temp[0][1] == temp[1][1]):
                for t in temp:
                    ans[t[0]] += (mm/2);
            # 1등과 2등이 점수가 같지 않은경우
            elif (temp[0][1] != temp[1][1]):
                ans[temp[0][0]] += mm;
                ans[temp[1][0]] += mm/3;
                ans[temp[2][0]] += mm/3;
                ans[temp[3][0]] += mm/3;
        # 3등과 4등이 점수가 같지 않은 경우
        elif (temp[2][1] != temp[3][1]):
            # 1 등과 2 등이 점수가 같은 경우
            if (temp[0][1] == temp[1][1]):
                ans[temp[0][0]] += (mm*2)/3;
                ans[temp[1][0]] += (mm*2)/3;
                ans[temp[2][0]] += (mm*2)/3;
           # 1등과 2등이 점수가 같지 않은경우
            elif (temp[0][1] != temp[1][1]):
                ans[temp[0][0]] += mm;
                ans[temp[1][0]] += mm/2;
                ans[temp[2][0]] += mm/2;

def dfs(level, idx, chance, ans):
    global chances;
    nowTeams = chances[level - 1];
    if idx == 0:
        temp = [nowTeams[0], 3,nowTeams[1], 0, nowTeams[idx + 2]];
    elif idx == 1:
        temp = [nowTeams[0], 1,nowTeams[1], 1, nowTeams[idx + 2]];
    elif idx == 2:
        temp = [nowTeams[0], 0,nowTeams[1], 3, nowTeams[idx + 2]];
    chance.append(temp);
    
    if (level == 6):
        calChance(chance, ans);
        chance.pop();
        return ;
    
    for i in range(3):
        if float(chances[level][i+2]) != 0:
            dfs(level + 1, i, chance, ans);
    chance.pop();


for i in range(3):
    if float(chances[0][i + 2]) != 0:
        dfs(1, i, [], ans);

for t in teams:
    print(ans[t]);