[Algo Rhythm🕺💃]BOJ 20170 - Commemorative Dice

문제 분석

주사위 게임을 하는 첫번째, 두번째 플레이어를 각각 A, B라고 하고 A와 B의 주사위 중 임의의 한 면에 적힌 숫자를 각각 $\alpha, \beta$라고 하자.

이때 주사위는 6면이기 때문에 A와 B가 주사위를 던져서 나올 수 있는 경우의 수는 $6 \times 6 = 36$이다.

그리고 A가 B를 이기는 경우의 수인 $N_{win}$은 $\alpha \gt \beta$를 만족하는 모든 $\alpha$의 수와 같다.

따라서, A가 B를 이길 확률은 $N_{win} \over 36$이다. 이때, 문제에서 요구하는 것은 '더이상 나눌 수 없는' 분수 형태로 출력하는 것이기 때문에 분자와 분모를 최대 공약수로 나눠서 출력해야 한다.

 

문제 풀이

A와 B의 주사위 정보를 각각 배열에 저장한 뒤, $\alpha \gt \beta$를 만족하는 $\alpha$의 수를 구한다.

그리고 분자와 분모의 최대 공약수를 구한 뒤 그것으로 나누어서 출력한다.

이때 최대 공약수를 구하기 위해 '2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.'는 성질을 이용한 유클리드 호제법을 사용했다.

유클리드 호제법에 대한 자세한 내용은 아래를 참고하길 바란다.

https://ko.wikipedia.org/wiki/유클리드_호제법

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

복잡도 분석

주사위 면의 수를 n, A가 이길 확률의 분자, 분모를 각각 a, b라고 하자.

이때 시간 복잡도와 공간 복잡도는 아래와 같다.

 

시간 복잡도 : $O(log(a + b))$

• 최대공약수를 구하기 위한 유클리드 호제법

공간 복잡도 : $O(n)$

• A와 B의 주사위에 대한 정보를 저장하는 배열

 

코드

 

문제 출처

https://www.acmicpc.net/problem/20170

20170번: Commemorative Dice