문제
풀이
아이디어
모든 경우의 수
총 6경기에 대해 승패무 3가지
3^6 = 729가지
충분히 계산 가능한 경우의 수
729가지의 경우에서 각 팀의 승점과 확률을 계산한 뒤 승점 1~2위의 팀에는 확률을 해당 더해주면, (2위와 3위가 승점이 같다면, 1/2씩 나눠서 2위 3위팀에 확률을 더해주면) 끝
더 나은 방법이 있는가?
예제처럼 확률이 0%인 분기가 있다면 해당 분기를 타는 경우는 계산을 멈춰도된다.
구현
시작
먼저 국가명을 그냥 0,1,2,3로 해쉬하고 승률 테이블을 만들자.
nation_dict = {v:i for i,v in enumerate(readline().split())}6개의 대결을 저장하자. 인풋이 마구잡이로 들어오니 편의를 위해 (0,1) (0,2) (0,3) (1,2) (1,3) (2,3)의 대결 순으로 저장될 수 있도록 한다.
for _ in range(6):
a, b, w, d, l = readline().split()
a, b = nation_dict[a], nation_dict[b]
if a > b:
a, b = b, a
w, l = l, w
P_dict[(a,b)] = list(map(float,[w,d,l]))P_dict는 a vs b에서 a의 입장에서의 승무패 확률을 담고 있다.
P_round 와 win_score, score, versus를 선언한다.
편의를 위해 짜다보니 변수가 조금 많다. (네이밍을 정확하게 하지않으면 오히려 헷깔릴때가 있다.)
P_round = [0,0,0,0] 은 i 번째 친구가 진출하는 확률을 저장
win_socre = [0,0,0,0]은 6번의 경기 동안 i번째 친구의 승점을 저장
score = [3,1,0]는 승점을 적용하려고 저장
versus = list(P_dict.keys())는
6경기의 순서를 저장하였다.
함수 dfs(i,win_score,P)
def dfs(i,win_score,P):
global P_round
if i == 6:
whogetround(win_score,P)
return
a,b = versus[i]
pp = P_dict[versus[i]]
for _ in range(3):
if pp[_] != 0:
win_score[a] += score[_]
win_score[b] += score[-1-_]
P *= pp[_]
dfs(i+1,win_score,P)
win_score[a] -= score[_]
win_score[b] -= score[-1-_]
P /= pp[_]평범한 dfs이다 6번의 경기동안 승무패를 for 문으로 돌려 모든 경우의 수를 계산한다. 다만 확률이 0인 경우에는 경우의 수 계산을 멈춘다. 어차피 최종적으로 1,2위에게 P를 더해주는데 P가 0이라서 의미가 없다.
이때까지는 명명법만 헷깔렸지 어렵지 않았다. i == 6이면 모든 경기가 끝난 것이니 1,2위를 정하기 위한 whogetround 함수를 구현하였다.
여기서 예외처리에 실수가 많아서 계속 문제를 틀렸었다. ㅜ
whogetround(win_score,P)
최종적으로 확률 P와 승점을 받아서 P_round에 진출 확률을 더해주는 함수.
def whogetround(win_score,P):
global P_round
max_1 = max_2 = max_3 = -1
max_1_idx = max_2_idx = max_3_idx = -1
# print(win_score)
for idx, x in enumerate(win_score):
# print(idx)
# print(max_1,max_2,max_3)
# print(max_1_idx,max_2_idx,max_3_idx)
if x > max_1:
max_3 = max_2
max_3_idx = max_2_idx
max_2 = max_1
max_2_idx = max_1_idx
max_1 = x
max_1_idx = idx
elif max_1 >= x > max_2:
max_3 = max_2
max_3_idx = max_2_idx
max_2 = x
max_2_idx = idx
elif max_2 >= x > max_3:
max_3 = x
max_3_idx = idx
max_4_idx = 6-(max_1_idx+max_2_idx+max_3_idx)
assert max_4_idx < 4, 'assert'
if win_score.count(max_1) == 4:
for _ in range(4):
P_round[_] += P/2
elif win_score.count(max_1) == 3:
for _ in [max_1_idx,max_2_idx,max_3_idx]:
P_round[_] += 2*P/3
elif win_score.count(max_2) == 3:
P_round[max_1_idx] += P
for _ in [max_2_idx,max_3_idx,max_4_idx]:
P_round[_] += P/3
elif win_score.count(max_1) == 2:
P_round[max_1_idx] += P
P_round[max_2_idx] += P
elif win_score.count(max_2) == 2:
P_round[max_1_idx] += P
for _ in [max_2_idx,max_3_idx]:
P_round[_] += P/2
else:
P_round[max_1_idx] += P
P_round[max_2_idx] += P
하.. 노가다... ㅎㅎ;; 그냥 처음부터
tmp = [[v,i] for i,v in enumerate(win_score)]로 idx와 value를 가진 2단 어레이를 만들고 소팅할 껄...
괜히 별거 없겠지 하고 공간을 아끼겠다는 생각에 제일 큰 값과 인덱스, 그 다음으로 큰 값과 인덱스만 구하면 끝이겠거니 생각하고 접근했다가 코드가 이렇게 늘어났다.
예외 케이스는 다음과 같다.
- A == B == C == D
모든 친구들에게 를 더해준다.
- A == B == C > D
A, B, C에 를 더해준다.
- A > B == C == D
A에는 P를 더하고, B,C,D에 를 더해준다.
- A > B == C > D
A에는 P를 더하고, B, C에 를 더해준다.
- 그 외 모든 경우
A와 B에 P를 더해준다.
여기까지는 몇번씩 틀려가면서 아 맞다 이 예외 했는데, 그 뒤로 모든 예외를 확인했건만 계속 틀렸었다.
문제는 count(max_v)로 같은 경우를 세면서 예외가 세는 경우가 있었다는 것.
elif win_score.count(max_2) == 3:
P_round[max_1_idx] += P
for _ in [max_2_idx,max_3_idx,max_4_idx]:
P_round[_] += P/3
# elif win_score.count(max_1) == 2:
# P_round[max_1_idx] += P
# P_round[max_2_idx] += P
elif win_score.count(max_2) == 2:
P_round[max_1_idx] += P
for _ in [max_2_idx,max_3_idx]:
P_round[_] += P/2
기존에는 위에 저 주석처리된 부분이 없어서,
A=B > C > D
인 경우가 win_score.count(max_2) == 2:에 걸리는 문제가 있었다.
그냥 처음부터 리스트를 새로 만들어서 소팅할껄 이게 뭔 고생인지 ㅜㅜ, 쉬운 길은 쉽게 가자.
결과
저 부분만 고쳤더니 바로 pass라서 다행이다.
뭐가 틀렸지 하면서 고생을 좀 많이했다. 특히 if문 떡칠을 하면 웬만한 예제로는 걸리게 하기가 어려우기도 하고
함수 자체를 테스트하지 않고, 혹시 다른 곳에 문제가 있나 문제 input을 바꿔가며 테스트하는데 확률 문제다 보니 이게 정답인지 나도 모른다는 것. 껄껄 멍청하게 디버깅을 하느라 시간을 많이 날렸다. 2018 코드 페스티벌 본선 첫 문제라는데 첫 문제부터 이렇게 어이 없이 고전하다니..
하지만 무지와 콘은 직접 확률을 계산하지 못했고, 여러분들에게 도움을 요청하였다. 무지와 콘을 도와 이 문제를 해결해보자!
미안해 무지야
