[BOJ 23974] 백준 23974번 - 짝수 게임
| Zero One Algorithm Contest 2021 풀이 | ||
|---|---|---|
| A | [BOJ 23971] ZOAC 4 | |
| B | [BOJ 23972] 악마의 제안 | |
| C | [BOJ 23973] 표적지 옮기기 | |
| D | [BOJ 23974] 짝수 게임 | |
| F | [BOJ 23976] 문자열 나누기 | |
| G | [BOJ 23977] To Find Password | |
| H | [BOJ 23978] 급상승 |
1. 문제
$23974$. 짝수 게임 (Zero One Algorithm Contest 2021 Open Contest D번)
2. 풀이
윤구를 $Y$라 하고, 한성을 $H$라 한다. 그 뒤 숫자는 가져간 동전 개수이며, $YG$는 윤구 승리, $HS$는 한성 승리이다. $N=0$이라고 가정하면, 윤구는 짝수 개의 동전을 가져야 한다.
$K=1 \rightarrow Y1,\;H0 \rightarrow HS$
$K=2 \rightarrow Y2,\;H0 \rightarrow YG$
$K=3 \rightarrow Y2,\;H1 \rightarrow YG$
$K=4 \rightarrow Y4,\;H0 \rightarrow YG$
$K=5 \rightarrow Y4,\;H1 \rightarrow YG$
윤구가 동전을 가져가서 짝수개가 됨과 동시에 동전이 $0$개 또는 $1$개가 남는다면, 한성이는 선택 권한이 없어 강제로 게임이 끝나게 됨을 알 수 있고 이는 윤구의 승리가 된다. $(K=2,3,4,5의 경우)$
반대로 한성이가 동전을 가져가서 동전이 $0$개 또는 $1$개가 남아서 게임이 강제로 끝나게 된다면 어떨까? 만약 그 시기에 윤구가 동전을 짝수개만큼 갖고 있었다면 한성이는 동전이 $1$개 남도록 할 것이고, 동전을 홀수개만큼 갖고 있었다면 한성이는 동전이 $0$개 남도록 하여 윤구가 패배하도록 할 것이다.
위를 통해 다음과 같은 사실을 알 수 있다.
$1.$ 총 동전이 짝수개인지 홀수개인지, 짝수개를 먹어야 하는지 홀수개를 먹어야 하는지, 지금 내가 혹은 상대방이 가진 동전이 짝수개인지 홀수개인지와 같은 사실들이 지금 해야 할 행동을 결정해준다.
동전은 $1$개 이상 $4$개 이하만큼 가져갈 수 있다. 따라서, 동전이 총 $K$개라면 이에 대한 결과는 동전이 총 $K-4$개, $K-3$개, $K-2$개, $K-1$개일 때의 결과와 연관이 있다. (이전 상태가 다음 상태를 결정해주는 다이나믹 프로그래밍)
$K-4$,$K-3$,$K-2$,$K-1$개일 때 게임을 시작한 사람이 전부 승리를 거머쥔다고 가정해보자. 동전이 총 $K$개가 있고 윤구 차례이다. 윤구는 $1\sim 4$개 중 얼만큼 동전을 가져가든 한성의 차례가 되고 한성이 승리하게 된다. 따라서 $K$개일 때는 게임을 시작한 사람이 패배하게 된다.
만약 $K-4$,$K-3$,$K-2$,$K-1$개 중 게임을 시작한 사람이 패배하는 경우가 $1$개라도 있다고 가정하자. 그럼 $K$개일 때 게임을 시작한 사람은 본인이 승리해야 하므로 다음 턴의 사람이 그 사람이 패배하는 경우가 선택되게 특정 개수만큼 먹을 수 있다. 그러므로 이 경우는 게임을 시작한 사람이 승리한다. 정리하면 다음과 같다.
$2.$ 이전 네 개의 상태 중 게임을 시작한 사람이 패배하는 경우가 적어도 하나 있는 경우 $\rightarrow$ 현재 상태는 게임을 시작한 사람이 승리함 이전 네 개의 상태 모두 게임을 시작한 사람이 승리하는 경우 $\rightarrow$ 현재 상태는 게임을 시작한 사람이 패배함
(위 사실은 백준에 있는 다른 거의 모든 동전 게임 문제에서 동일하게 적용된다.)
$1$의 사실로 미루어보아 총 동전이 짝수개인 경우와 홀수개인 경우를 나눠볼 수 있다.
총 동전이 짝수개라고 가정해보자. 또, 어떤 사람($A$)이 동전을 짝수 개 먹어야 이긴다고 가정해보자. 그럼 다른 사람($B$)은 동전을 홀수 개 먹어야 $A$가 짝수 개를 먹지 못하게 해서 본인이 이길 수 있다. 반대로 $A$가 동전을 홀수 개 먹어야 이긴다고 가정하면, $B$는 동전을 짝수 개 먹어야 한다. 이렇게 생각해보면 총 네 가지 경우가 나온다.
$(1)$ 총 동전이 짝수 개이고 어떤 사람이 동전을 짝수 개 먹어야 이긴다. $(2)$ 총 동전이 짝수 개이고 어떤 사람이 동전을 홀수 개 먹어야 이긴다. $(3)$ 총 동전이 홀수 개이고 어떤 사람이 동전을 짝수 개 먹어야 이긴다. $(4)$ 총 동전이 홀수 개이고 어떤 사람이 동전을 홀수 개 먹어야 이긴다.
$(1)$의 경우를 생각해보자. 총 동전이 $K(K\%2=0)$개일 때 시작한 플레이어가 동전을 짝수 개 먹어야 이긴다. 그렇다면 상대방 입장에서는 동전을 홀수 개 먹어야 이긴다.
따라서, 총 동전이 $K-1$,$K-2$,$K-3$,$K-4$개일 때 시작한 플레이어가 동전을 홀수 개 먹어야 이기는 상황에서, 시작한 플레이어가 패배하는 경우를 찾아내야 한다. 이는 $(2),(3),(4)$에서도 동일하게 적용된다.
동전을 짝수 개 먹어야 이기는 상황을 $E$, 동전을 홀수 개 먹어야 이기는 상황을 $O$라고 하면 이렇게 정리할 수 있다. 탐색은 $2$의 방법을 가져온다.
- $K\%2=0$, $E$ $\rightarrow$
(K-1, O)(K-2, O)(K-3, O)(K-4, O)탐색 - $K\%2=0$, $O$ $\rightarrow$
(K-1, E)(K-2, E)(K-3, E)(K-4, E)탐색 - $K\%2=1$, $E$ $\rightarrow$
(K-1, E)(K-2, E)(K-3, E)(K-4, E)탐색 - $K\%2=1$, $O$ $\rightarrow$
(K-1, O)(K-2, O)(K-3, O)(K-4, O)탐색
배열에 저장해서 위와 같은 방식으로 dp를 사용하여 순서대로 만들어가면 정답에 도달할 수 있다. $(10,000,000 $ $\times 2 $ $\times 1byte(bool)$ $=20MB)$
그게 아니면 적당히 해보고 규칙을 찾는 방법도 있다. 모든 게임에서 윤구가 먼저 시작하므로, 해당 차례에 승리하는 플레이어를 써넣는다.
| K | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| E | H | Y | Y | Y | Y | Y | H | Y | Y | Y | Y | Y | H |
| O | Y | Y | Y | Y | H | H | Y | Y | Y | Y | H | H | Y |
$E$의 경우는 $K\%6=1$ 이면 $H$승, 아니면 $Y$의 승이다. $O$의 경우는 $K\%6=0$ or $5$ 이면 $H$승, 아니면 $Y$의 승이다.
여기서 $E$라는 건 결국 $N=0$일 때 시작한다는 것이고, $O$라는 건 $N=1$일 때 시작한다는 것임을 의미한다.
물론 이 경우만 보고 일반화를 확정 지을 수는 없지만, 특정 주기로 계속 반복된다는 사실은 알기 때문에 이 방법을 사용할 수 있다. 위의 규칙을 명확한 공식을 통해 일반화하는 방법이 있는지에 대해서는 좀 더 연구가 필요하다.
3. 채점 결과
4. 회고
.
댓글남기기