[BOJ 24517] 백준 24517번 - 카드 게임과 쿼리
1. 문제
$24517$. 카드 게임과 쿼리 (2022 ICPC Sinchon Winter Algorithm Camp Contest J번)
백준 24517번 - 카드 게임과 쿼리 (https://www.acmicpc.net/problem/24517)
2. 풀이
돌 가져가기 게임이고, $Q\leq 100,000$인데 $1$초($10$억번의 연산)만에 연산하기 위해서는 다음과 같은 방법이 있다.
- 각 쿼리가 입력 값들을 변수로 하는 어떤 단순 방정식으로 $O(1)$만에 계산된다.
- 모든 경우에 대해 dp값을 미리 저장하여 각 쿼리가 $O(1)$만에 처리된다.
- 각 쿼리마다 dp 값을 갱신하며 정답을 찾는다.
문제 유형마다 또는 주어지는 쿼리마다 차이는 있지만, 쿼리 개수가 일정 개수를 넘어가면 $2$와 $3$은 방법만 다를 뿐 시간복잡도는 비슷하다고 추정한다.
이 문제는 $1$의 방법은 불가능하여 dp를 사용해야 한다. 그런데 $1\leq A\lt B\leq 10^9$이므로 공간이 부족하다. 따라서 공간복잡도를 줄일 방법을 문제에서 찾아내야 한다.
선택한 카드는 사라지며 사용할 수 없는 카드가 없다면, 다시 $K$개의 카드를 놓는다. 모든 카드를 사용하는 것을 ‘한 턴’이라고 부르면, 한 턴당 사용하는 카드의 총합은 $1$부터 $K$까지의 합이다. 모든 턴에서 이 총합은 동일하기 때문에, 동일한 결과값들이 턴을 주기로 반복적으로 나타난다는 것을 알 수 있다.
만일 이전까지 홀수 번 게임이 진행되었다면, 게임을 시작하는 사람이 달라지기 때문에 정확히는 반복적이지 않다. 일단 문제를 이해하기 위해 이를 넘어가고 마지막에 서술하고자 한다.
턴을 주기로 결과값들이 동일하기 때문에, 한 턴에서의 결과만 저장하면 된다. $K$의 최댓값은 $10$이기 때문에 한 턴의 카드 총합의 최댓값은 $55$이다.
한 턴 안에서 어떤 카드를 사용했는지에 따라서 이번에 수행할 수 있는 작업이 달라진다. 따라서 dp에는 합의 값 뿐만 아니라 어떤 카드가 남아있는지에 대한 정보가 필요하다. 이를 bitmask로 나타낸다.
$n$은 사용된 카드의 총합, $bm$(bitmask)은 사용된 카드의 정보라고 두면, $dp[n][bm]$은 $1\leq k\leq N$인 모든 $k$에 대해 $dp[n-k][bm\;\&\sim(1\lt\lt k)]$에서 온다고 볼 수 있다.
기존 돌 가져가기 문제와 동일하게 본인이 어떤 선택을 하든 패배하는 수 밖에 없는 경우, 현재 단계에서 패배한다. 따라서 이기면 $1$, 지면 $0$을 return 하게 하고, 모든 $dp[n-k][bm\;\&\sim(1\lt\lt k)]$의 값들을 bitwise and 시킨다.
$1$ $\rightarrow$ 모든 이전 dp값의 결과가 ‘1’ -> 모든 경우에서 상대방이 승리한다 -> 어떤 선택을 하든 패배한다. -> 현재 dp의 결과값이 ‘0’이 되어야 함
$0$ -> 최소 1개의 ‘0’ dp값이 존재한다. -> 어떤 경우에서 상대방이 패배한다 -> 해당 루트를 선택하여 승리 가능 -> 현재 dp의 결과값이 ‘1’이 되어야 함
따라서, 모든 dp를 bitwise and한 값을 $1$과 xor시키면$(0\rightarrow 1,1\rightarrow 0)$, 현재 단계에서 원하는 결과값이 나온다는 것을 알 수 있다.
마지막 예외처리를 해주어야 한다. 앞에서 반복되는 작업을 동일하게 보고 ($B-A$)를 ($1\sim K$의 합)만큼 나눈 정도의 작업만 수행하였다. 그러나 이는 완벽한 반복이 아니다.
만일 처리하지 않은 반복된 모든 작업(임의의 카드를 고르는 행동)의 개수가 홀수개라면, 반복이 아닌 작업의 시작점이 swoon이 아니라 raararaara가 되어버리기 때문이다. 따라서 반복된 모든 작업의 개수가 홀수개인 경우는 최종 결과를 뒤집어야 한다.
3. 채점 결과
4. 회고
예외처리를 만드는 과정에서 WA를 받았다.
댓글남기기