https://school.programmers.co.kr/learn/courses/30/lessons/258709?language=python3

숫자가 다양한 주사위가 2n개 있고, A와 B가 n개씩 고를 때 A가 더 많이 승리할 수 있는 주사위 조합을 찾는 문제이다.

Python

from itertools import combinations, product

def solution(dice):
    answer = []
    
    cases = list(combinations(range(len(dice)), len(dice)//2))
    
    nums = list(product(range(6), repeat = len(dice)//2))
    
    
    score = dict()
    for i, case in enumerate(cases):
        score[i] = []
        
        for n in nums:
            tmp = 0
            for idx, d in enumerate(n):
                tmp += dice[case[idx]][d]
                
            score[i].append(tmp)

        score[i].sort()

    
    ans = [0, -1]
    for a in range(len(cases)):
        b = len(cases) - a -1
        tmp = 0
        for sa in score[a]:
            start = 0
            end = len(score[b])-1
            while start <= end:
                mid = (start + end) // 2
                
                if score[b][mid] >= sa:
                    end = mid - 1
                else:
                    start = mid + 1
            tmp += start
        if tmp > ans[0]:
            ans = [tmp, a]
        
                    
    ans = list(cases[ans[1]])
    
    for a in range(len(ans)):
        ans[a] += 1
    return ans

완전탐색을 해야하나 고민하다가 다른 방법이 없어서 질문하기를 확인했는데, 10C5의 경우가 252이고, 5^6의 경우가 7776이어서 완전탐색 해도 된다고 해서 그렇게 진행하였다.

combinations로 10C5의 모든 경우를 찾았다. 그리고 각 주사위별로 어떤 면이 나오는지 조합을 구했는데 itertools의 product를 사용했다. product는 처음 사용해봤는데 카테시안 곱을 해주는 함수라고 한다.

그래서 주사위 면이 나오는 조합을 nums에 저장하고, score라는 딕셔너리를 생성해서 주사위 고르는 case별로 점수어떻게 나오는지 기록하고 정렬하였다.

A가 고르는 주사위와 B가 고르는 주사위는 겹침이 없어야하는데, 10C5로 뽑은 조합을 정렬하게되면 가운데를 기준으로 대칭되는 곳에 있는 case들은 서로 상보적인 관계를 갖게 된다.

이를 활용하여서 b의 case를 len(cases)-a-1로 구하였다.

a가 이기는 경우를 계산하기 위해 b의 점수에 대해서 이진탐색을 진행하였다.

여기서 이진탐색 조건을 설정하면서 처음에는

if score[b][mid] > sa

로 했으나 이때는 실패했었다. 왜 안되지 하다가

if score[b][mid] >= sa

로 변경하였는데 통과할 수 있었다.

이진탐색 조건설정에 대해서 조금 더 연구를 해봐야겠다.

---

왜 그랬는지 이해했다.
구하려는 답은 sa가 score[b]보다 큰 경우이고 이를 start에 저장하게 되는데

if score[b] > sa:
	end = mid - 1

이렇게 되면 start는 score[b] == sa인 경우도 포함되게 된다.
그래서 이를 end에 넣어주기 위해

if score[b] >= sa:

로 해준 것이었다.

예전부터 고민이었는데 어느정도 해결된 것 같다.