A와 B가 n개의 주사위를 가지고 승부를 합니다. 주사위의 6개 면에 각각 하나의 수가 쓰여 있으며, 주사위를 던졌을 때 각 면이 나올 확률은 동일합니다. 각 주사위는 1 ~ n의 번호를 가지고 있으며, 주사위에 쓰인 수의 구성은 모두 다릅니다.
A가 먼저 n / 2개의 주사위를 가져가면 B가 남은 n / 2개의 주사위를 가져갑니다. 각각 가져간 주사위를 모두 굴린 뒤, 나온 수들을 모두 합해 점수를 계산합니다. 점수가 더 큰 쪽이 승리하며, 점수가 같다면 무승부입니다.
A는 자신이 승리할 확률이 가장 높아지도록 주사위를 가져가려 합니다.
다음은 n = 4인 예시입니다.
주사위구성
| #1 | [1, 2, 3, 4, 5, 6] |
| #2 | [3, 3, 3, 3, 4, 4] |
| #3 | [1, 3, 3, 4, 4, 4] |
| #4 | [1, 1, 4, 4, 5, 5] |
- 예를 들어 A가 주사위 #1, #2를 가져간 뒤 6, 3을 굴리고, B가 주사위 #3, #4를 가져간 뒤 4, 1을 굴린다면 A의 승리입니다. (6 + 3 > 4 + 1)
A가 가져가는 주사위 조합에 따라, 주사위를 굴린 1296가지 경우의 승패 결과를 세어보면 아래 표와 같습니다.
A의 주사위승무패
| #1, #2 | 596 | 196 | 504 |
| #1, #3 | 560 | 176 | 560 |
| #1, #4 | 616 | 184 | 496 |
| #2, #3 | 496 | 184 | 616 |
| #2, #4 | 560 | 176 | 560 |
| #3, #4 | 504 | 196 | 596 |
A가 승리할 확률이 가장 높아지기 위해선 주사위 #1, #4를 가져가야 합니다.
주사위에 쓰인 수의 구성을 담은 2차원 정수 배열 dice가 매개변수로 주어집니다. 이때, 자신이 승리할 확률이 가장 높아지기 위해 A가 골라야 하는 주사위 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 승리할 확률이 가장 높은 주사위 조합이 유일한 경우만 주어집니다.
코드 구조
get_case 함수
get_case 함수는 주어진 주사위 배열을 입력으로 받아, 해당 주사위들의 합산 결과가 나올 빈도를 기록합니다. 예를 들어 주사위가 [1, 2, 3]이라면, 모든 경우의 수를 더해 결과를 저장하는 방식입니다.
from collections import defaultdict
def get_case(players):
case = defaultdict(int)
case[0] = 1 # 초기값 설정 (아직 주사위를 굴리지 않은 상태)
for dice_num in players:
new_case = defaultdict(int)
for prev_sum, freq in case.items():
for num in dice[dice_num]:
new_case[prev_sum + num] += freq
case = new_case
return casesolution 함수
이 함수에서는 주어진 dice 배열을 반으로 나누어 모든 가능한 팀 조합을 생성하고, 각 팀의 승리, 패배, 무승부 빈도를 계산합니다. combinations를 사용하여 팀을 구성하며, 그 중 최대 승률을 가지는 팀을 찾습니다.
from itertools import combinations
def solution(dice):
max_win = 0
answer = []
dice_case = list(combinations([i for i in range(len(dice))], len(dice) // 2))
set_case = [[dice_case[i], dice_case[-1-i]] for i in range(len(dice_case) // 2)]
for A, B in set_case:
case_a = get_case(A)
case_b = get_case(B)
win, lose, draw = 0, 0, 0
for a_dice in case_a.keys():
for b_dice in case_b.keys():
count = case_a[a_dice] * case_b[b_dice]
if a_dice > b_dice:
win += count
elif a_dice < b_dice:
lose += count
else:
draw += count
# 승리 횟수가 최대인 경우 answer 업데이트
if max_win < win:
max_win = win
answer = [n + 1 for n in A]
if max_win < lose:
max_win = lose
answer = [n + 1 for n in B]
return answer코드 작동 방식
- 플레이어 조합 생성: dice_case에서 모든 가능한 플레이어조합을 생성합니다. 예를 들어 주사위가 6개라면 3개씩의 조합을 통해 두 개의 팀을 구성합니다.
- 각 플레이어 의 합산 결과 계산: get_case 함수를 통해 각 플레이어의 주사위 합산 결과와 빈도를 defaultdict로 계산합니다.
- 플레이어 승리 횟수 계산: 각 팀의 합산 결과를 비교하여 승리, 패배, 무승부 빈도를 구합니다. 그중 가장 승률이 높은 플레이어를 기록합니다.
- 최종 승리 팀 반환: 가장 승률이 높은 플레이어를 answer에 저장하여 반환합니다.
