문제
문제 설명
A와 B가 n개의 주사위를 가지고 승부를 합니다. 주사위의 6개 면에 각각 하나의 수가 쓰여 있으며, 주사위를 던졌을 때 각 면이 나올 확률은 동일합니다. 각 주사위는 1 ~ n의 번호를 가지고 있으며, 주사위에 쓰인 수의 구성은 모두 다릅니다.
A가 먼저 n / 2개의 주사위를 가져가면 B가 남은 n / 2개의 주사위를 가져갑니다. 각각 가져간 주사위를 모두 굴린 뒤, 나온 수들을 모두 합해 점수를 계산합니다. 점수가 더 큰 쪽이 승리하며, 점수가 같다면 무승부입니다.
A는 자신이 승리할 확률이 가장 높아지도록 주사위를 가져가려 합니다.
다음은 n = 4인 예시입니다.
| 주사위 | 구성 |
|---|---|
| #1 | [1, 2, 3, 4, 5, 6] |
| #2 | [3, 3, 3, 3, 4, 4] |
| #3 | [1, 3, 3, 4, 4, 4] |
| #4 | [1, 1, 4, 4, 5, 5] |
- 예를 들어 A가 주사위 #1, #2를 가져간 뒤 6, 3을 굴리고, B가 주사위 #3, #4를 가져간 뒤 4, 1을 굴린다면 A의 승리입니다. (6 + 3 > 4 + 1)
A가 가져가는 주사위 조합에 따라, 주사위를 굴린 1296가지 경우의 승패 결과를 세어보면 아래 표와 같습니다.
| A의 주사위 | 승 | 무 | 패 |
|---|---|---|---|
| #1, #2 | 596 | 196 | 504 |
| #1, #3 | 560 | 176 | 560 |
| #1, #4 | 616 | 184 | 496 |
| #2, #3 | 496 | 184 | 616 |
| #2, #4 | 560 | 176 | 560 |
| #3, #4 | 504 | 196 | 596 |
A가 승리할 확률이 가장 높아지기 위해선 주사위 #1, #4를 가져가야 합니다.
주사위에 쓰인 수의 구성을 담은 2차원 정수 배열 dice가 매개변수로 주어집니다. 이때, 자신이 승리할 확률이 가장 높아지기 위해 A가 골라야 하는 주사위 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 승리할 확률이 가장 높은 주사위 조합이 유일한 경우만 주어집니다.
제한사항
- 2 ≤ dice의 길이 = n ≤ 10
- n은 2의 배수입니다.
- dice[i]는 i+1번 주사위에 쓰인 6개의 수를 담고 있습니다.
- dice[i]의 길이 = 6
- 1 ≤ dice[i]의 원소 ≤ 100
입출력 예
| dice | result |
|---|---|
| [[1, 2, 3, 4, 5, 6], [3, 3, 3, 3, 4, 4], [1, 3, 3, 4, 4, 4], [1, 1, 4, 4, 5, 5]] | [1, 4] |
| [[1, 2, 3, 4, 5, 6], [2, 2, 4, 4, 6, 6]] | [2] |
| [[40, 41, 42, 43, 44, 45], [43, 43, 42, 42, 41, 41], [1, 1, 80, 80, 80, 80], [70, 70, 1, 1, 70, 70]] | [1, 3] |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
| 주사위 | 구성 |
|---|---|
| #1 | [1, 2, 3, 4, 5, 6] |
| #2 | [2, 2, 4, 4, 6, 6] |
A가 주사위 #2를 가져갔을 때 승리할 확률이 가장 높습니다. A가 #2, B가 #1 주사위를 굴린 결과에 따른 승패는 아래 표와 같습니다.
| 주사위 결과 | 1 (B) | 2 (B) | 3 (B) | 4 (B) | 5 (B) | 6 (B) |
|---|---|---|---|---|---|---|
| 2 (A) | 승 | 무 | 패 | 패 | 패 | 패 |
| 2 (A) | 승 | 무 | 패 | 패 | 패 | 패 |
| 4 (A) | 승 | 승 | 승 | 무 | 패 | 패 |
| 4 (A) | 승 | 승 | 승 | 무 | 패 | 패 |
| 6 (A) | 승 | 승 | 승 | 승 | 승 | 무 |
| 6 (A) | 승 | 승 | 승 | 승 | 승 | 무 |
입출력 예 #3
| 주사위 | 구성 |
|---|---|
| #1 | [40, 41, 42, 43, 44, 45] |
| #2 | [43, 43, 42, 42, 41, 41] |
| #3 | [1, 1, 80, 80, 80, 80] |
| #4 | [70, 70, 1, 1, 70, 70] |
A가 가져가는 주사위 조합에 따라, 주사위를 굴린 1296가지 경우의 승패 결과를 세어보면 아래 표와 같습니다.
| A의 주사위 | 승 | 무 | 패 |
|---|---|---|---|
| #1, #2 | 704 | 16 | 576 |
| #1, #3 | 936 | 24 | 336 |
| #1, #4 | 360 | 24 | 912 |
| #2, #3 | 912 | 24 | 360 |
| #2, #4 | 336 | 24 | 936 |
| #3, #4 | 576 | 16 | 704 |
따라서 A가 주사위 #1, #3을 가져갔을 때 승리할 확률이 가장 높습니다.
풀이
너무 어렵다 .....
다른 사람의 풀이를 이해하는 데 초점을 맞춰보았다.
1. A가 n개 중에 n//2개를 뽑을 수 있는 경우의 수 : nC(n//2)
n = len(dice)
cases = list(combinations(range(n), n//2)) # A가 주사위를 뽑는 경우의 수 nC(n//2) - list로n = len(dice)일 때, range(n)의 역할
dice = [
[1, 2], # 0번 주사위
[3, 4], # 1번 주사위
[5, 6], # 2번 주사위
[7, 8] # 3번 주사위
]
n = len(dice) # n = 4여기서 range(n)을 사용하면 range(4) = [0, 1, 2, 3]이 되는데,
즉, 주사위 인덱스 리스트 [0, 1, 2, 3]에서 조합을 구하는 것과 같기 때문에 range(n)을 사용해야한다.
list를 사용하는 이유
combinations()가 기본적으로 한 번만 순회 가능한 이터레이터를 반환하기 때문에 list로 반환해서 계속 사용할 수 있도록 하자.
ex) [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
2. 뽑은 주사위 조합에서 나올 수 있는 모든 합의 경우의 수를 구하기
product() : 두 개 이상의 리스트의 모든 조합을 구할 때
itertools.product()는 두 개 이상의 리스트에서 가능한 모든 조합(순서 고려)을 만들어 주는 함수
💡 "반복 가능한 객체(iterable)들의 데카르트 곱(Cartesian Product)을 구해주는 함수"
마찬가지로 이터레이터를 반환하므로 list()로 캐스팅해서 저장해주어야 계속 사용할 수 있다.
ex)
from itertools import product
a = [1, 2]
b = [3, 4]
result = list(product(a, b)) # 두 리스트에서 가능한 모든 조합 생성
print(result)출력 ⬇️
[(1, 3), (1, 4), (2, 3), (2, 4)]활용 ⬇️
A = [] # 각 조합별 합의 경우의 수 저장 리스트
for case in cases:
# 선택된 주사위들의 값 가져오기
selected_dice = [dice[i] for i in case]
# 모든 가능한 조합의 합을 구하고 정렬
all_sums = sorted(sum(comb) for comb in product(*selected_dice))
# 결과 리스트에 추가
A.append(all_sums)입력 ex)
dice = [
[1, 2], # 0번 주사위
[3, 4], # 1번 주사위
[5, 6], # 2번 주사위
[7, 8] # 3번 주사위
]출력 ex)
cases = [(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)]
A[0] = [4, 5, 5, 6] # (0,1) 선택
A[1] = [6, 7, 7, 8] # (0,2) 선택
A[2] = [8, 9, 9, 10] # (0,3) 선택
A[3] = [8, 9, 9, 10] # (1,2) 선택
A[4] = [10, 11, 11, 12] # (1,3) 선택
A[5] = [12, 13, 13, 14] # (2,3) 선택3. cases 정렬되어 있기 때문에 cases에서 A가 선택한 것의 대칭인 것을 B가 고르게 된다.
ex) cases 가 다음과 같을 때
cases = [(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)]
A[0] = (0,1) <=> B[5] = (2,3)
A[1] = (0,2) <=> B[4] = (1,3)
A[2] = (0,3) <=> B[3] = (1,2)이를 활용한 코드 ⬇️
a, counts = 0, len(A) # a: 최댓값 저장, counts: 조합 개수
for i in range(counts):
B = A[counts - i - 1] # A[i]의 반대편 조합을 가져옴 (대칭되는 B)| A[i] | B = A[counts - i - 1] |
|---|---|
| A[0] | A[5] |
| A[1] | A[4] |
| A[2] | A[3] |
4. 이진 탐색을 활용한 A의 승리 횟수 계산
B가 정렬되어 있으므로 성능 상 완점탐색 대신 이진탐색(Binary Search)으로 하자 !
left가 최종적으로 t보다 작은 B의 원소 개수를 의미한다.
left 값을 temp에 더해주면 A[i]의 승리 횟수를 빠르게 구할 수 있다.
temp = 0 # A[i]가 B보다 이기는 횟수
for t in A[i]: # A[i]의 각 값 t에 대해
left = 0
right = len(B) - 1
while left <= right: # 이진 탐색 시작
mid = (left + right) // 2 # 중앙값 찾기
if B[mid] < t: # B[mid]가 t보다 작으면
left = mid + 1 # 탐색 범위를 오른쪽으로 이동
else:
right = mid - 1 # 탐색 범위를 왼쪽으로 이동
temp += left # B에서 t보다 작은 값의 개수를 left가 가리킴ex) 목표: A[i]의 값 하나씩 가져와서 B에서 몇 개의 값이 더 작은지 찾기.
A[i] = [6, 7, 9] # 현재 선택한 조합의 합
B = [3, 5, 8, 10] # 상대 조합의 합 (정렬됨)첫 번째 값 t = 6 탐색
B = [3, 5, 8, 10]
B에서 6보다 작은 값 개수는 2개 → temp += 2
두 번째 값 t = 7 탐색
B = [3, 5, 8, 10]
B에서 7보다 작은 값 개수는 2개 → temp += 2
세 번째 값 t = 9 탐색
B = [3, 5, 8, 10]
B에서 9보다 작은 값 개수는 3개 → temp += 3
최종 결과
temp = 2 + 2 + 3 = 7
5. 가장 승리 확률이 높은 조합 찾기
# 가장 승리 확률이 높은 조합 찾기
if a < temp: # 현재 저장된 최대 승리 횟수 a보다 더 높은 temp를 발견하면 갱신
a = temp # 최대 승리 횟수 업데이트
answer = [x + 1 for x in cases[i]] # 1-based index로 변환하여 저장. 1번부터!최종코드
from itertools import combinations, product
def solution(dice):
n = len(dice)
answer = []
cases = list(combinations(range(n), n//2)) # A가 주사위를 뽑는 경우의 수 nC(n//2)
# combinations()가 기본적으로 한 번만 순회 가능한 이터레이터를 반환하기 때문에 list로 반환해서 계속 사용할 수 있도록 하자.
# ex) cases = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
A = [] # 각 조합별 합의 경우의 수 저장 리스트
for case in cases:
# 선택된 주사위들의 값 가져오기
selected_dice = [dice[i] for i in case]
# 모든 가능한 조합의 합을 구하고 정렬
all_sums = sorted(sum(comb) for comb in product(*selected_dice))
# 결과 리스트에 추가
A.append(all_sums)
# ex)
# A[0] = [4, 5, 5, 6] # (0,1) 선택
# A[1] = [6, 7, 7, 8] # (0,2) 선택
# A[2] = [8, 9, 9, 10] # (0,3) 선택
# A[3] = [8, 9, 9, 10] # (1,2) 선택
# A[4] = [10, 11, 11, 12] # (1,3) 선택
# A[5] = [12, 13, 13, 14] # (2,3) 선택
a, counts = 0, len(A) # a: 최댓값 저장, counts: 조합의 개수
for i in range(counts):
B = A[counts - i - 1] # A[i]의 반대편 조합을 가져옴 (대칭되는 B)
temp = 0 # A[i]가 B보다 이기는 횟수
for t in A[i]: # A[i]의 각 값 t에 대해
left = 0
right = len(B) - 1
while left <= right: # 이진 탐색 시작
mid = (left + right) // 2 # 중앙값 찾기
if B[mid] < t: # B[mid]가 t보다 작으면
left = mid + 1 # 탐색 범위를 오른쪽으로 이동
else:
right = mid - 1 # 탐색 범위를 왼쪽으로 이동
temp += left # B에서 t보다 작은 값의 개수를 left가 가리킴
# 가장 승리 확률이 높은 조합 찾기
if a < temp: # 현재 저장된 최대 승리 횟수 a보다 더 높은 temp를 발견하면 갱신
a = temp # 최대 승리 횟수 업데이트
answer = [x + 1 for x in cases[i]] # 1-based index로 변환하여 저장. 1번부터!
return answer