p_주사위고르기_258709

브루드포스

문제

주사위 n 개
n/2 개씩 각각 가질때
각각의 나오는 숫자과 확률 개수구해서 주사위 조합당 평균을 비교하면 되지않을까..

1. 일단 주사위의 조합을 구해보자.

답

# <span id="dic길이-한자리수"></span>dic길이 한자리수
dic_comb = {} # 각주사위별 숫자조합
comb_idx = []

def solution(dice):
    answer = []
    visited = [0] * len(dice)
    find_combin(visited,0,0,{},dice)
    # print(dic_comb)
    # print(comb_idx)
    winner = [-1,-1] # 주사위, 확률
    for left,right in comb_idx:
        win = 0
        lose = 0
        for k1,v1 in dic_comb[left]:
            for k2,v2 in dic_comb[right]:
                if k1>k2:
                    win += v1 * v2
                elif k1<k2:
                    lose += v1 * v2
        if win > lose and winner[1]<win:
            winner[0] = left
            winner[1] = win
        elif win < lose and winner[1] < lose:
            winner[0] = right
            winner[1] = lose
        # print(winner)
    return list(map(lambda x: int(x)+1,winner[0]))

def find_combin(visited,ind,depth,current,dice):
    leng = len(visited)
    # print(visited,depth,current)
    if depth >= leng/2:
        global dic_comb
        global comb_idx
        tmpv = ""
        tmpl = ""
        for i in range(leng):
            if visited[i]:
                tmpv += str(i)
            else:
                tmpl += str(i)
        if tmpv[0] == '0':
            comb_idx.append((tmpv,tmpl))
        clisted= list(current.items())
        clisted.sort()
        dic_comb[tmpv] = clisted
        return
    for i in range(ind,leng):
        if visited[i]:
            continue
        visited[i] = 1
        tmpc = {}
        for j in dice[i]:
            if current:
                for key,value in current.items():
                    if key+j in tmpc:
                        tmpc[int(key)+j] += value
                    else:
                        tmpc[int(key)+j] = value
            else: 
                if j in tmpc:
                    tmpc[j] +=1
                else:
                    tmpc[j] = 1
        find_combin(visited,i,depth+1,tmpc,dice)
        visited[i] = 0