A Request to God for the Turn and River

두 플레이어의 홀 카드와 플랍으로 이미 사용된 카드는 $7$장이다. 따라서 턴이나 리버로 선택할 수 있는 카드는 $52-7=45$장이다. 턴과 리버의 순서가 구분되고 두 카드는 서로 달라야 하므로 가능한 선택은

$$45\times 44=1980$$

개뿐이다. 모든 경우를 직접 확인해도 충분히 작다.

각 턴, 리버 선택에 대해 두 플레이어의 최종 $7$장 패를 평가한다. $7$장 중 실제로 사용하는 카드는 $5$장이므로, 모든

$$\binom{7}{5}=21$$

개의 $5$장 조합을 평가하고 그중 가장 강한 패를 선택하면 된다.

$5$장 패는 다음과 같은 정수 배열로 나타낼 수 있다.

$$(\text{족보 번호},\ \text{첫 번째 비교값},\ \text{두 번째 비교값},\ldots)$$

족보가 강할수록 족보 번호를 크게 두고, 같은 족보 안에서는 텍사스 홀덤의 동률 비교 순서대로 값을 저장한다. 그러면 배열의 사전식 비교만으로 두 패의 우열을 판단할 수 있다. 예를 들어 포카드는

$$(7,\ \text{포카드 랭크},\ \text{키커},\ 0,\ 0,\ 0)$$

처럼 나타낼 수 있다.

스트레이트를 판정할 때는 에이스가 높은 경우와 $\texttt{A2345}$의 휠 스트레이트를 따로 처리한다. 플러시, 풀하우스, 트리플, 투 페어, 원 페어와 하이 카드도 문제의 비교 규칙에 맞추어 비교값을 채운다.

선택한 턴 카드가 원래 턴 카드와 정확히 같으면 턴 비용은 $0$이고, 그렇지 않으면 선택한 카드의 랭크 비용을 낸다. 리버도 같은 방식이다.

모든 턴, 리버 쌍을 검사하면서 승리하는 경우의 최소비용과 무승부인 경우의 최소비용을 각각 저장한다. 승리하는 경우가 하나라도 있으면 승리의 최소비용 답을 출력한다. 승리가 없다면 무승부의 최소비용 답을 출력하고, 둘 다 없다면 -1을 출력한다.

한 테스트 케이스에서 확인하는 경우의 수는 항상 상수이므로 시간 복잡도는 $O(1)$, 추가 공간 복잡도도 $O(1)$이다. 전체 입력에 대해서는 시간 복잡도가 $O(T)$이다.

Solution written by GPT5.6