[BOJ 23974 // C++] 짝수 게임

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 23974번 문제인 짝수 게임이다.

문제는 아래 링크를 확인하자.

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

23974번: 짝수 게임

이 게임에서 현재 윤구의 차례인 경우, 윤구가 어떤 경우에 이길 수 있는지를 잘 생각해보자.

 

1. 윤구가 짝수개의 동전을 앞으로 가져와야 하는 경우, 다음 중 적어도 하나 이상의 상황을 만족해야 윤구가 이길 수 있다.

(1) 윤구가 한 개의 동전을 가져오고 상대가 다음에 동전을 1~4개 중 어떤 개수로 가져가도 앞으로 항상 홀수 개의 동전을 가져올 수 있다.

(2) 윤구가 두 개의 동전을 가져오고 상대가 다음에 동전을 1~4개 중 어떤 개수로 가져가도 앞으로 항상 짝수 개의 동전을 가져올 수 있다.

(3) 윤구가 세 개의 동전을 가져오고 상대가 다음에 동전을 1~4개 중 어떤 개수로 가져가도 앞으로 항상 홀수 개의 동전을 가져올 수 있다.

(4) 윤구가 네 개의 동전을 가져오고 상대가 다음에 동전을 1~4개 중 어떤 개수로 가져가도 앞으로 항상 짝수 개의 동전을 가져올 수 있다.

 

2. 윤구가 홀수개의 동전을 앞으로 가져와야 하는 경우, 다음 중 적어도 하나 이상의 상황을 만족해야 윤구가 이길 수 있다.

(1) 윤구가 한 개의 동전을 가져오고 상대가 다음에 동전을 1~4개 중 어떤 개수로 가져가도 앞으로 항상 짝수 개의 동전을 가져올 수 있다.

(2) 윤구가 두 개의 동전을 가져오고 상대가 다음에 동전을 1~4개 중 어떤 개수로 가져가도 앞으로 항상 홀수 개의 동전을 가져올 수 있다.

(3) 윤구가 세 개의 동전을 가져오고 상대가 다음에 동전을 1~4개 중 어떤 개수로 가져가도 앞으로 항상 짝수 개의 동전을 가져올 수 있다.

(4) 윤구가 네 개의 동전을 가져오고 상대가 다음에 동전을 1~4개 중 어떤 개수로 가져가도 앞으로 항상 홀수 개의 동전을 가져올 수 있다.

 

위의 내용을 코드로 구현하여 초기값을 집어넣고 K에 따라 윤구가 이길지 질지를 출력해보면 규칙을 발견할 수 있다. 그 규칙을 코드로 작성하여 문제를 해결하자.

 

아래는 규칙을 발견하기 위해 사용한 코드이다.

#include <iostream>
using namespace std;

int odd[1000];
int even[1000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	odd[1] = odd[2] = odd[3] = odd[4] = odd[7] = 1;
	even[0] = even[2] = even[3] = even[4] = even[5] = even[6] = 1;
	for (int i = 8; i < 1000; i++) {
		if (odd[i - 2] && odd[i - 3] && odd[i - 4] && odd[i - 5]) even[i] = 1;
		if (even[i - 3] && even[i - 4] && even[i - 5] && even[i - 6]) even[i] = 1;
		if (odd[i - 4] && odd[i - 5] && odd[i - 6] && odd[i - 7]) even[i] = 1;
		if (even[i - 5] && even[i - 6] && even[i - 7] && even[i - 8]) even[i] = 1;

		if (even[i - 2] && even[i - 3] && even[i - 4] && even[i - 5]) odd[i] = 1;
		if (odd[i - 3] && odd[i - 4] && odd[i - 5] && odd[i - 6]) odd[i] = 1;
		if (even[i - 4] && even[i - 5] && even[i - 6] && even[i - 7]) odd[i] = 1;
		if (odd[i - 5] && odd[i - 6] && odd[i - 7] && odd[i - 8]) odd[i] = 1;
	}
	
	for (int i = 0; i < 1000; i++) cout << even[i] << ' ';
	cout << '\n';
	for (int i = 0; i < 1000; i++) cout << odd[i] << ' ';
}