BOJ 17080 결함 게임

문제 링크입니다.

전략 고정하기

선공의 입장에서 후공이 할 행동을 항상 고정할 수 있다면 게임을 꽤 주도적으로 풀어갈 수 있을 것이라 생각할 수 있습니다.

돌이 충분히 많이 있다고 생각하고, 선공이 할 수 있는 수를 생각합시다. 만약 선공이 크기가 2인 돌을 바닥에 놓는다면, 후공은 자신의 전략이 뭐든 간에 규칙 상 크기가 1인 돌을 그 위에 놓는 것밖에 할 수 없습니다.

선공의 입장에서, 크기가 2인 돌과 4인 돌을 순서대로 바닥에 놓는 것으로 앞에서부터 4개의 돌을 마치 처음부터 없었던 것처럼 만들 수 있습니다. 따라서 1~4개의 돌이 있을 때 선공이 이길 수 있는 경우들에서는 거기에 돌이 4k개씩 추가되어도 항상 선공이 이길 수 있습니다.

• 돌이 1개인 경우, 2개인 경우는 자명하게 선공 필승입니다.
• 돌이 4개인 경우, 2-1-3-4와 같은 순서로 돌을 놓으면 3개의 돌탑이 만들어지므로 선공 필승입니다.
• 돌이 3개인 경우는 선공이 어느 돌을 놓아도 후공이 그에 반응할 수 있습니다.
  • 선공이 크기가 1인 돌을 놓았으면 크기가 3인 돌을 옆에 놓습니다.
  • 이외에는 선공이 놓은 돌 위에 크기가 1인 돌을 놓습니다.

따라서 돌의 개수를 4로 나눈 나머지가 3이 아니라면 선공이 이깁니다.

후공 필승?

돌의 개수가 4로 나눈 나머지가 3인 경우에 선공이 이길 수 있는지 생각해 봅시다.

만약 선공이 처음에 크기가 1인 돌을 놓는다면, 후공의 입장에서는 돌 개수를 4로 나눈 나머지가 2인 상황에서 선공을 잡은 것과 상황이 같습니다. 따라서 선공이 처음에 크기가 1인 돌을 두는 건 안 됩니다.

크기가 2 이상인 돌을 처음에 둬 봅시다. 후공은 그 크기가 뭐든 간에 크기가 1인 돌을 위에 올려둡니다. 여기서 선공이 다시 크기가 제일 작은 돌을 두면, 돌은 4의 배수 개가 남았고 후공이 먼저 수를 둘 수 있습니다. 후공은 두 번째로 작은 돌을 바닥에 두는 것을 반복해 짝수 개의 돌탑을 추가로 만들고 이길 수 있습니다.

선공은 다시 위에 돌을 쌓을 수 있는 돌을 놓습니다. 후공은 가장 작은 돌을 그 위에 올리고, 그러면 돌탑 둘을 제외하고 나면 처음의 상황과 완전히 같아집니다. 따라서 최종적으로는 돌이 3개만 남은 상황에서 선공의 차례가 되고, 이 경우는 항상 후공이 승리함을 알 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n;
	cout << (n%4 == 3 ? 2 : 1);
}