[프로그래머스] 주사위 고르기

문제

---

• 주사위 고르기 (LV3)

주사위 고르기

n개의 주사위 중에서 a와 b가 각각 절반씩 주사위를 나누어 가지고 주사위 게임을 한다.
각자 가지고 있는 모든 주사위를 던져서 던진 주사위의 합이 더 크면 이기는 게임이다.
해당 게임을 할 때 승리할 확률이 가장 높은 주사위 조합을 찾는 문제였다.
n이 최대 10까지여서 시간 복잡도는 널널한 문제였다.

내 코드

---

보기에는 굉장히 쉽게 풀릴 것 같았는데 생각보다 잘 풀리지 않았다.
그래서 단순 작은 n을 활용하여서 단순 구현으로 시도해 보았는데 이마저도 쉽지 않았다.
그래서 힌트를 찾던 도중 아래 글을 확인하였다.

해당 글을 읽고 비슷한 방식으로 구현해보니 통과할 수 있었다.

from itertools import combinations, product

def solution(dice):
    answer = []
    temp_score = 0
    divides = combinations(range(len(dice)), len(dice) // 2)
    
    for divide in divides:
        a_sum = [0]
        b_sum = [0] 
        
        for i in range(len(dice)):
            if i in divide:
                a_sum = [sum(comb) for comb in product(dice[i], a_sum)]
            else:
                b_sum = [sum(comb) for comb in product(dice[i], b_sum)]
        
        a_sum.sort()
        b_sum.sort()
        score = 0
        a = 0
        b = 0
        
        while a < len(a_sum) and b < len(b_sum):
            if a_sum[a] > b_sum[b]:
                score += len(a_sum) - a
                b += 1
            else:
                a += 1
        
        if score > temp_score:
            temp_score = score
            answer = [s + 1 for s in divide]
    
    return answer

리스트에서 하나씩 뽑아서 새로운 리스트를 생성하는데 itertools의 product를 처음 사용해보았다.
여러가지 모듈을 사용해보고 익혀두어야겠다는 생각이 들었다.