[백준 17080] 결함게임

문제

https://www.acmicpc.net/problem/17080

17080번: 결함 게임

 

문제 풀이

• 각 플레이어는 턴마다, 만약 현재 보드 위에 있는 돌탑 중 어딘가에 올릴 수 있는 돌이 남아있다면, 반드시 그러한 돌들 중 하나를 골라 올릴 수 있는 돌탑 중 원하는 돌탑 위에 올린다.
• 만약 어떤 돌탑에도 돌을 올릴 수 없다면, 남아있는 돌 중 아무거나 하나를 골라 보드 위에 새로운 돌탑의 바닥을 만든다.
• 모든 돌이 소진된 뒤, 돌탑의 개수가 홀수이면 선공이 이기며, 짝수이면 후공이 이긴다.

위 조건들을 생각하며 돌의 개수를 한 개씩 늘려보면 아래의 규칙을 찾을 수 있습니다.

 

1.  k개의 돌을 둬서 후공이 이겼다면 (k + 1)개의 돌을 두면 선공이 이긴다 ( ∵ 선공이 1을 두고 후공이 남은 k개를 최선을 다해서 쌓아도 후공이 쌓은 돌탑의 개수는 짝수개이므로 전체 돌탑의 개수는 홀수)

 

2. 돌의 개수 3개를 시작으로 4개의 주기마다 후공이 승리함.

 

코드

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

int n;

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	if (n % 4 == 3) cout << 2;
	else cout << 1;
}