728x90
- 2024 KAKAO WINTER INTERNSHIP
combi = []
perm = []
def solution(dice):
leng = len(dice)
generate(leng, [], 0, 0)
permu(leng / 2, [], 0)
max_winrate = 0
max_dice = []
count = 0
for arr in combi:
b_arr = []
for i in range(leng):
if i not in arr:
b_arr.append(i)
red = {}
blue = {}
for p in perm:
a_val = 0
for i in range(len(arr)):
a_val += dice[arr[i]][p[i]]
red[a_val] = red.get(a_val, 0) + 1
b_val = 0
for i in range(len(b_arr)):
b_val += dice[b_arr[i]][p[i]]
blue[b_val] = blue.get(b_val, 0) + 1
#print(red, blue)
s_red = sorted(red.items(), key = lambda item: item[0])
s_blue = sorted(blue.items(), key = lambda item: item[0])
red_win = 0
for aVal in s_red:
for bVal in s_blue:
if aVal[0] > bVal[0]:
red_win += aVal[1] * bVal[1]
win_rate = red_win / pow(6, leng)
if win_rate > max_winrate:
max_winrate = win_rate
#print(arr)
max_dice = arr
return list(map(lambda x: x + 1, max_dice))
# A가 가져갈 주사위
def generate(leng, buck, count, start):
if count == leng / 2:
combi.append(buck.copy())
return
for i in range(start, leng):
buck.append(i)
generate(leng, buck, count+1, i+1)
buck.pop()
# 주사위가 나올 경우의 수
def permu(max, buck, count):
if max == count:
perm.append(buck.copy())
return
for i in range(6):
buck.append(i)
permu(max, buck, count+1)
buck.pop()완전탐색으로 풀 경우 효율 '시간초과'가 발생한다.
예를 들어, 4개의 주사위를 굴린다면 모든 주사위를 고려할 경우 6^4의 경우의 수이지만
A가 2개의 주사위를 픽한 결과의 값과 B가 픽한 결과의 값을 사전에 저장해 비교하면 훨씬 줄어든 경우의 수로 대처 가능하다.
