BOJ 26074 곰곰이와 테트리스

문제 링크입니다.

모방하기

후공이 점수 상 이기고 있고 상대가 놓은 블록을 계속 똑같이 놓는다면 두 플레이어의 점수 차는 좁혀지지 않습니다. 그러니 후공으로서는 가능하다면 선공의 수를 모방하는 전략을 쓰고 싶습니다.

선공의 입장에서, 자신이 블록을 하나 두면 후공에게 점수로 이기고 있고 자신이 후공인 것처럼 행동할 수 있습니다. 판에 블록 하나를 둠으로써 선공이 항상 후공의 수를 따라 둘 수 있는 상태로 만들 수 있다면 선공이 필승입니다.

모방할 수 있게 조작하기

항상 상대의 수와 중심을 기준으로 점대칭인 곳에 블록을 두는 것으로 상대의 수를 모방할 수 있습니다. 따라쟁이 바둑이라고도 불리는 전략입니다. 실제 바둑에서는 상대가 정중앙에 돌을 두어 이를 깰 수 있지만, 지금은 선공이 중앙을 차지하는 블록을 두는 것으로 오히려 따라쟁이 바둑을 둘 수 있는 상태로 만들 수 있습니다.

이것이 가능한 경우를 찾아 봅시다. 판의 가로 세로 길이가 모두 홀수인 경우, 1×1 짜리 블록 (8번 블록)을 정중앙에 두는 것으로 따라쟁이 바둑을 만들 수 있습니다. 가로 세로 길이가 모두 짝수인 경우도 2×2 짜리 블록 (4번 블록)을 두면 됩니다.

한쪽은 홀수, 다른 쪽은 짝수인 경우가 조금 다른데, 보통은 S자형 블록(5번 블록)을 중앙에 놓는 것으로 따라쟁이 바둑이 가능하게 만들 수 있습니다. S자형을 놓을 수 없는 1×(짝수)의 경우에는 I자형 블록 (1번 블록)을 두면 가능합니다. 이마저도 불가능한 경우로는 1×2 짜리 판이 유일한데, 이 경우 두 플레이어가 각각 8번 블록을 놓는 것 외의 수가 없어 유일하게 후공 필승입니다.

관찰한 결과대로 간단하게 구현하면 문제를 해결할 수 있습니다.

코드

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

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n, m; cin >> n >> m;
	if(n > m) swap(n, m);
	cout << (n == 1 && m == 2 ? "ChongChong" : "GomGom");
}