돌 $N$개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개를 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람이 누구인지를 구하여라. 게임은 상근이가 먼저 시작한다.
돌이 1, 3, 4개인 경우는 상근이가 돌을 1개 가져가면 상근이가 승리한다.
나머지도 채워보자.
2개인 경우는 1 - 1개 순서로 가져가 창영이가 승리한다.
5개인 경우는 3 - 1 - 1개 순서로 가져가 상근이가 승리한다.
6개인 경우는 4 - 1 - 1개 순서로 가져가 상근이가 승리한다.
7개인 경우는 1 - 4 - 1 - 1개 순서로 가져가 상근이가 승리한다.
...
이런 식으로 게임이 진행될 것이다.
6개인 경우에서 1개를 가져가는 것은 턴이 바뀐 상태로 5개인 게임판에서 게임을 다시 진행하는 것과 같다.
만약, 6개인 게임판에서 돌을 1개 가져가는 행동만 할 수 있는 경우, 5개인 게임판으로만 갈 수 있고 5개인 게임판에서 A가 승리하는 결과라면 6개인 게임판에서는 A는 반드시 패배한다.
지금 위의 문제에서 나온 형태는 1, 3, 4개가 줄어든 게임판으로 갈 수 있다. 해당 게임판으로 갔을 때의 선공이 지는 경우가 하나라도 존재하면 현재 게임판에서는 선공이 승리한다.
1개 게임판은 선공이 승리한다.
2개 게임판은 1개 게임판으로만 이동 가능하다. 선공이 승리하는 경우만 있으므로 2개 게임판은 선공이 패배한다.
3개 게임판은 0, 2개 게임판으로 이동 가능하다. 0개 게임판과 2개 게임판 모두 선공이 패배하는 게임판이다. 즉, 3개 게임판은 선공이 승리한다.
4개 게임판은 0, 1, 3개 게임판으로 이동 가능하다. 0개 게임판은 선공이 패배하는 게임판이다. 플레이어는 완벽하게 플레이하기에 이기려고 한다. 즉, 0개 게임판으로 이동한다. 4개 게임판은 선공이 승리하는 게임판이다.
... 이런식으로 채워나가면 된다.
결국, 7로 나눈 나머지가 0 또는 2인 경우를 제외하고는 상근이가 승리한다.
'알고리즘' 카테고리의 다른 글
| [BOJ 22858] 원상 복구 (small) (0) | 2024.04.02 |
|---|---|
| [BOJ 11508] 2+1 세일 (0) | 2024.04.01 |
| [BOJ 2056] 작업 (0) | 2024.03.29 |
| [BOJ 2992] 크면서 작은 수 (0) | 2024.03.29 |
| [BOJ 1448] 삼각형 만들기 (0) | 2024.03.28 |