문제 링크

풀이과정

• A와 B가 뽑은 주사위의 조합이 정해졌다고 가정합시다.
• 가장 쉬운 방법은, A의 주사위 눈의 합과 B의 주사위 눈의 합을 구해서 비교하는 것입니다.
  • 예를 들어, 문제 예시에 따라 A는 #1, #3번 주사위를, B는 #2, #4번 주사위를 뽑았다고 합시다.
  • 이때, **A는 1, 3번 주사위를 통해 눈 [1, 4]**를 B는 **2, 4번 주사위를 통해 눈 [3, 5]**를 뽑았다고 가정하면, A는 총점 5 / B는 총점 8을 획득했으므로 B가 승리합니다.
  • 이러한 과정을 주사위를 선택하는 모든 경우에 대하여, 그리고 선택한 주사위에서 나올 수 있는 모든 눈의 조합에 대하여 계산할 수 있습니다.
• 해당 방법대로 시간 복잡도를 계산해보겠습니다.
  • 주사위 최대 갯수는 10개입니다.
  • 따라서, 주사위를 선택하는 모든 경우의 수는 **10C5(최댓값)**입니다.
  • 이제, 선택된 주사위의 조합이 정해졌다고 가정합시다.
  • A도 주사위 5개, B도 주사위 5개를 가지고 있으므로, **가능한 주사위 눈 조합의 경우의 수는 (6^5 * 6^5)**입니다.
  • 그러므로, 최악의 경우 시간 복잡도는 10C5 * (6^5 * 6^5) 로서, 시간 초과 가능성이 존재합니다. (C는 Combination, ^는 거듭제곱을 의미합니다.)
• 따라서, 시간 복잡도 이슈를 피하기 위해서 다른 방법을 생각해야 합니다.
• 우리는 A와 B의 주사위 눈을 함께(연쇄적으로) 구하여 주사위 눈의 합을 구하고, 비교하는 과정을 수행했습니다.
• 이때, A가 낼 수 있는 주사위 눈의 조합과 B가 낼 수 있는 주사위 눈의 조합을 따로 구하면 어떨까요?
  • 즉, 10C5 * (6^5 * 6^5)를 10C5 * 6^5의 시간 복잡도로 낮추는 것입니다.
• 그 다음, 다음 과정을 수행합니다.
  1. A의 주사위를 통해 가능한 모든 주사위 눈의 합을 구하고, B도 동일한 과정을 반복합니다. (각각 리스트 자료 구조로 관리합니다)
  2. A와 B의 리스트(원소: 주사위 눈의 합)를 오름차순으로 정렬합니다.
  3. A의 리스트를 순회하면서, 현재 주사위 눈의 합을 통해, B를 이길 수 있는 경우의 수를 구합니다.
  4. 3에서 구한 경우의 수를 합산합니다.
• 이를 위해, 조합과 이분 탐색으로 문제를 접근해보겠습니다.

전체 코드

from itertools import combinations, product

def solution(dice):
    '''
    A가 이기는 것을 기준으로 함.
    '''
    answer = []
    dice_indices = [i for i in range(len(dice))]  # 주사위 인덱스
    pickup_num = int(len(dice) / 2)  # 뽑을 주사위 갯수
    win_max = 0

    for a_dices in combinations(dice_indices, pickup_num):
        a_dices = set(a_dices)   # A가 뽑은 주사위 집합 (ex: (1, 2))
        b_dices = set(dice_indices) - a_dices  # B가 뽑은 주사위 집합 (ex: (3, 4))
        
        ### A와 B 따로따로 계산 수행 ###
        # A, B 각각 나올 수 있는 주사위 눈의 조합
        itemsA = [dice[a_idx] for a_idx in a_dices]  # ex 2
        itemsB = [dice[b_idx] for b_idx in b_dices]  # ex 2
        product_listA = list(product(*itemsA))  # 6^2
        product_listB = list(product(*itemsB))  # 6^2
        winA = 0  # A가 승리할 수 있는 방법의 수
        
        # A, B 각각 주사위 눈의 조합으로 얻을 수 있는 숫자 합
        sum_tempA, sum_tempB = [], []
        
        # A에 대하여, 가능한 주사위 눈의 숫자 합을 저장
        for a in product_listA:   sum_tempA.append(sum(list(a)))
        # B에 대하여, 가능한 주사위 눈의 숫자 합을 저장
        for b in product_listB:   sum_tempB.append(sum(list(b)))
        
        # A, B에 대한 주사위 숫자 합 정렬
        sum_tempA = sorted(sum_tempA)
        sum_tempB = sorted(sum_tempB)
          
        for target in sum_tempA:
            # target이 B의 주사위 눈 합의 최솟값보다 작은 경우
            if target <= sum_tempB[0]:  continue 
            # target이 B의 주사위 눈 합의 최댓값보다 큰 경우
            if target > sum_tempB[-1]:  
                winA += len(sum_tempB)
                continue
            
            ### 이분 탐색 수행 ###
            left, right = 0, len(sum_tempB) - 1
            find = 0
            while left <= right:
                mid = (left + right) // 2
                if target > sum_tempB[mid]:
                    left = mid + 1
                elif target < sum_tempB[mid]:
                    right = mid - 1
                # target을 B에서 찾아도, 동일한 값이 이전 인덱스에도 존재할 수 있습니다.
                # 우리는 A가 이기는 경우(점수가 높은 경우)만을 고려해야 합니다.
                # 따라서, right를 줄여서 계속 이분 탐색을 수행해야 함을 잊지 마세요!
                else:
                    find = mid
                    right = mid - 1
            
            # A가 이길 수 있는 방법의 수 갱신
            if find != 0:   winA += find
            else:   winA += (right + 1)
                        
        # 갱신된 방법의 수가 최댓값인 경우
        if winA > win_max:  
            answer = [idx+1 for idx in a_dices]
            win_max = winA

    return sorted(answer)

유사 문제

이분 탐색은 다음과 같은 조건 하에서 특정 값을 찾아내기 위하여 생각해볼 수 있는 해결책입니다.

• 순차 탐색에 필요한 시간이 과도하게 많이 드는 경우
• 탐색 대상이 정렬되어 있는 경우