BOJ 9611 돌 게임 7

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

9661번: 돌 게임 7

 

문제.

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 4^x개 만큼 가져갈 수 있다. 즉, 가능한 개수는 1, 4, 16, 64, ...개 이다. 4^x개만큼 돌을 가져갈 수 있는 방법이 없는 사람이 게임을 지게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

 

입력.

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000)

 

풀이.

상대 플레이어가 돌을 몇 개 가져가던 관계 없이 두 플레이어가 가져가는 돌의 합이 5의 배수가 되도록 할 수 있다.

4^n은 5로 나눈 나머지가 1 또는 -1이기 때문에 상대가 나머지 1인 돌 개수를 가져갔다면 4개를, 상대가 나머지 -1인 돌 개수를 가져갔다면 1개를 가져가는 것으로 해결가능하다.

따라서 탁자 위에 돌의 개수가 4개 이하인 경우만 살펴 주면 되고, 돌의 개수가 0개 또는 2개인 경우가 지는 경우이다. 따라서 n을 5로 나눈 나머지에 따라 답을 출력할 수 있다.

 

이런 류의 게임에서는 상대가 가져간 돌의 개수와 반대되는 개수를 가져갈 수 있도록 반복 단위를 설정할 수 있다면 쉽게 해결된다.