BOJ 24678 돌 무더기 게임

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

24678번: 돌무더기 게임 1

문제.

3개의 돌무더기에 돌이 각각 x,y,z 개 있다. R과 B가 이 돌무더기에서 게임을 한다. 각 플레이어는 다음의 한 가지 시행만을 할 수 있다.

• 돌이 있는 두 개의 돌무더기를 골라, 돌을 하나씩 가져가고, 나머지 하나의 돌무더기에 돌을 하나 추가한다.

더 이상 시행을 할 수 없는 사람이 이긴다.

R와 B가 최선을 다했을 때 이기는 사람을 출력하여라. 게임은 R이 먼저 시작한다.

 

입력.

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.

다음 T줄에 각각 세 개의 정수 x, y, z가 주어진다.

 

제한.

•  1≤T≤200000
•  1≤x,y,z ≤10^9

풀이.

x,y,z 범위로 생각했을 때 DP로는 해결 불가능하다.

 

각 플레이어가 할 수 있는 행동은 다음과 같다.

	x	y	z
x에 추가	+1	-1	-1
y에 추가	-1	+1	-1
z에 추가	-1	-1	+1

어...? 각 행동을 할 때 마다 전체 돌의 개수는 1개 줄어든다.

a = x+y, b = y+z, c = z+x로 두자. 그러면 행동에 따른 돌의 개수 변화는 다음과 같다.

	x	y	z	a	b	c
x에 추가	+1	-1	-1	0	-2	0
y에 추가	-1	+1	-1	0	0	-2
z에 추가	-1	-1	+1	-2	0	0

문제를 변형해보면, 돌무더기 a, b, c에서 한 번에 두개씩만 가져갈 수 있는 게임이 된다.

각 돌무더기에서는 최대 a/2, b/2, c/2번 가져갈 수 있다. 또, 더 이상 게임을 진행할 수 없다는 것은 "a, b, c중 어느 하나의 돌의 개수가 0인 것"과 같다.

 

예를 들어 a가 0이 되었다면 a=x+y이고 x, y는 0보다 큰 정수이므로 x=0,y=0이 되기 때문에 원래 문제에서의 "돌이 있는 두 개의 돌무더기를 골라"를 할 수 없기 때문이다. b 또는 c가 2 이상일지라도 z에서 두 개의 돌을 가져갈 수 없다.

 

따라서 a/2+b/2+c/2-2번 가져가고 나면 그 다음 플레이어는 게임을 진행할 수 없게 된다. 처음 가져가는 플레이어가 R이므로 a/2+b/2+c/2-2가 짝수이면 R, 홀수이면 B가 승리한다.

다시 식을 정리하자. a/2+b/2+c/2=(a+b+c)/2-(a,b,c중 홀수의 개수)/2=(x+y+z)-(x, y, z가 모두 홀수 또는 짝수이면 0, 아니면 1)이고, 이 값의 홀짝 여부에만 종속되므로 (x, y, z의 홀수 개수) - (x,y,z가 모두 홀수 또는 짝수이면 0, 아니면 1)와 같다.

x,y,z의 경우의 수에 대해 표로 정리하면

x	y	z	결과
홀	홀	홀	홀
홀	홀	짝	홀
홀	짝	짝	짝
짝	짝	짝	짝

과 같고, 결과가 홀수일 때 B, 짝수일 때 R이 승리하는 것과 같다.

 

문제를 보자마자 전체 돌의 개수가 1씩 감소하는 것을 확인하고 더하고 빼고 하다보면 한 돌무더기에서만 돌을 가져가는 문제로 변형할 수 있어 보여 시도해서 정답을 얻었습니다.