주사위의 개수가 최대 10개 입니다. 10개의 주사위로 A와 B가 승부를 한다면, 이중에 5개를 고를 수 있죠. 우선은 2개의 주사위를 사용해서, 나올 수 있는 모든 경우의 수를 구하는 방법을 알아 보겠습니다.
[1, 2, 3, 4, 5, 6] [1, 2, 3, 4, 5, 6] 이렇게 2개의 주사위가 있구요.
첫번째 주사위의
1을 [1, 2, 3, 4, 5, 6]에 모두 더하면, [2, 3, 4, 5, 6, 7]
2를 [1, 2, 3, 4, 5, 6]에 모두 더하면, [3, 4, 5, 6, 7, 8]
3를 [1, 2, 3, 4, 5, 6]에 모두 더하면, [4, 5, 6, 7, 8, 9]
4를 [1, 2, 3, 4, 5, 6]에 모두 더하면, [5, 6, 7, 8, 9, 10]
5를 [1, 2, 3, 4, 5, 6]에 모두 더하면, [6, 7, 8, 9, 10, 11]
6을 [1, 2, 3, 4, 5, 6]에 모두 더하면, [7, 8, 9, 10, 11, 12]
2개의 주사위로 나올 수 있는 경우의 수를 모두 모아 보면
[2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12] 가 됩니다.
이런식으로 5개의 주사위를 고름으로서, 나오는 숫자의 총 길이는 5 x 5 x 5 x 5 x 5가 되구요,
$$ 5^5 = 3125 $$ 길이는 3125 입니다. A가 가진 숫자의 총 길이는 3125이고, B도 3125 이구요, 서로 비교해서 이긴 경우의 수를 찾는 다고 하면 3125의 3125제곱 입니다. 엄청 나게 큰 숫자가 나오기 때문에, 시간안에 문제를 풀 수 없습니다.
숫자의 길이를 줄여야만 이 문제를 시간안에 풀 수 있습니다.
2개의 주사위로 나올 수 있는 경우의 수로 돌아가 보겠습니다.
[2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12]
같은 숫자가 반복되는 것을 볼 수 있습니다. 따라서, 숫자를 적고, 이 숫자의 길이를 적는 방법으로 길이를 줄 일 수 있습니다.
2(1개), 3(2개), 4(3개), 5(4개), 6(5개), 7(6개) ... 이런식으로 표현하는 것 입니다.
이런 방법을 run-length encoding 이라고 합니다.
A가 4(3개) 있고, B는 3(2개) 있다고 가정하고, 이기는 수를 계산해 보겠습니다.
4 > 3 이기 때문에 A 가 이기는 것이 구요, 3개 x 2개 = 6개 해서, A가 6번 이기게 됩니다.
이런 방식으로 이기는 횟수를 계산하게 되면, 보다 빠르게 계산 할 수 있습니다.
이제 주사위를 고르는 방법을 알아보겠습니다. 최대 10개의 주사위가 있으므로, 5개까지 고를 수 있습니다. 그러면 주사위를 고르는 경우의 수는 조합으로는 아래와 같이 표시 할 수 있습니다.
$$ _{10}C_{5} = \frac{10!}{(10-5)!5!} = 252 $$
주사위의 조합은 252개 입니다. O(n)을 계산하기 편하게 300 으로 좀 크게 잡고, 대략 A 가 300가지 경우의 수, B 가 300가지 경우의 수가 있다고 볼 수 있습니다.
300 x 300 은 90000 으로 그렇게 큰 숫자는 아닙니다. 하지만 여기에 주사위 숫자의 길이를 곱해야 합니다.
주사위 숫자의 길이는 알 수 없지만, run-length encoding 으로 길이를 줄였기 때문에 시간안에 문제를 풀 수 있을 것으로 예상해 봅니다.
댓글 없음:
댓글 쓰기