[PS]2024 카카오 겨울 인턴십 - 주사위 고르기

프로그래머스

문제

- 난이도: Level 3

- 승리 확률이 높아지기 위해 A가 골라야 하는 주사위 번호 구하기

풀이

문제의 입출력 예제에서 설명하듯,

가져가는 주사위의 조합에 따라 주사위를 굴린 경우의 수에서

승패 결과를 모두 세어 그중 승리 경우가 많은 주사위 조합을 골라야 한다.

제한사항

• 2 ≤ dice의 길이 = n ≤ 10
  • n은 2의 배수입니다.
  • dice[i]는 i+1번 주사위에 쓰인 6개의 수를 담고 있습니다.
  • dice[i]의 길이 = 6
  • 1 ≤ dice[i]의 원소 ≤ 100

접근 방식

구해야 하는 과정을 순서화 해보자면 아래와 같다.

 

1. n개의 주사위를 두 개의 조합으로 나누는 조합의 수 구하기

2. 조합 당 주사위의 면에서 나올 숫자에 따라 A, B의 승패 확률 계산하기

3. 승리할 확률이 가장 높은 주사위 조합 구하기

 

예제에서도 2개의 주사위로 1296가지의 경우의 승패 결과를 말하고 있고,

얼핏 보기만 해도 엄청 많은 경우의 수를 계산해야함을 알 수 있다.

이 경우의 수들을 어떻게 효율적으로 구할 수 있을까?

 

(1) n개의 주사위를 두 개의 조합으로 나누는 조합의 수 구하기

2 이상 10 이하의 주사위를 두 개의 조합으로 나누는 경우의 수는 nCn/2 이다.

하지만 이 과정에서 불필요한 중복을 제거할 수 있다.

 

예시를 들어보자.

dice = {1, 2, 3, 4} 로, 4개의 주사위가 있다.

A가 주사위를 가져가는 조합은 {1, 2} {2, 3} {3, 4} {2, 4}, {1, 3}, {1, 4}로 총 6가지이다.

 

이 6개 조합에서 각 주사위 면이 나오는 36가지 경우의 수를 다 구해야할까?

잘 생각해보면 불필요한 중복을 제거할 수 있다.

 

A가 {1, 2}를 가져가는 경우는 B가 {3, 4}를 가져가는 경우이다.

따라서 {1, 2}를 가져갔을 때 반대되는 {3, 4} 조합의 승리 확률은

1(100%) - {1, 2}의 승리 확률로 생각할 수 있다.

A가 {1, 2}를 가져가서 이길 확률 = 1 - B가 {3, 4}를 가져가서 이길 확률
B가 {1, 2}를 가져가서 이길 확률 = 1 - A가 {1, 2}를 가져가서 이길 확률

 

A가 {1, 2}를 가져가서 이길 확률이 30% 였다면, 나머지인 {3, 4}를 가져가서 이길 확률은 70%이다.

그렇다면 {3, 4}를 가져가서 이길 확률은 계산하지 않아도 1 - A가 {1, 2}를 가져가서 이길 확률인 70%이다.

 

따라서 모든 조합을 다 볼 필요 없이 조합의 절반만 확인하면 된다.

예를 들어 6개의 조합이 있다면, 3개만 확인하고

나머지는 1 - 상대 조합의 확률로 유추할 수 있다.

 

(2) 주사위의 조합에 따라 승패 계산하기

각각의 조합에 대해 A가 가진 주사위로 만들 수 있는 모든 합을 구한다.

B도 동일하게 모든 합을 구한 뒤,

A의 합이 B의 합보다 클 때 해당 조합의 승리 횟수를 +1 카운트한다.

 

(3) 해당 주사위 조합에서 승리할 확률이 가장 높은 주사위 조합을 구한다

각각의 조합마다 승, 패 횟수가 나왔으면 확률로 계산한 뒤

승리 확률이 가장 높은 조합을 찾으면 정답이 도출된다.

 

코드

1. 조합 구하기

c++에서는 next_permutation을 이용해서 조합을 구할 수 있다.

 

#include <iostream>

 

회고

문제 이해하는데만 시간이 꽤나 걸리는 것 같다..

그래도 입출력 예제 자세히 보면 이해는 잘 가서 좋은데

조건이 까다로운게 많아서 구현보다 그게 더 시간이 걸리는 느낌