백준 11565: 바이너리 게임

 

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

11565번: 바이너리 게임

 

 

문자열 a에서 1의 개수를 ca라고 하고 문자열 b에서 1의 개수를 cb라고 하자.

 

ca가 홀수인 경우 parity(a)가 1이기 때문에 문자열 끝에 1을 추가할 수 있다.

그러면 parity(a)가 0이 된다. 이러면 문자열 끝에 0을 맘껏 추가할 수 있다.

문자열 앞에서부터 1을 지울 때까지 숫자를 계속 지우면 parity(a)가 1이 된다. 그러면 또 문자열 끝에 1을 추가할 수 있다.

다만, 어떻게 해도 만든 문자열에서 1의 개수가 ca+1보다 커질 수는 없다.

 

그래서 일단 cb>ca+1인 경우는 무조건 DEFEAT이다.

반면 cb<=ca+1인 경우는 무조건 VICTORY이다. 아까 그 과정을 거치면 어떤 문자열이든 만들 수 있기 때문이다.

 

ca가 짝수인 경우도 마찬가지다.

이땐 문자열 끝에 parity(a), 즉 0을 맘껏 추가하거나

문자열 앞에서부터 1을 지울 때까지 숫자를 계속 지워서 parity(a)를 1로 만든 뒤 문자열 끝에 1을 추가하는 식으로

ca>=cb이기만 한다면 b를 완성시키는 것이 무조건 가능하다.

반대로 ca<cb이면 무조건 DEFEAT이다.

 

C언어로 구현한 것:

#include<string.h>

int main()
{
	char a[1004];
	char b[1004];
	scanf("%s", a);
	scanf("%s", b);
	int ca = 0;
	int cb = 0;
	for (int i = 0;i < strlen(a);i++)
	{
		if (a[i] == '1')
			ca++;
	}
	for (int i = 0;i < strlen(b);i++)
	{
		if (b[i] == '1')
			cb++;
	}

	if (ca % 2 == 0)
	{
		if (ca >= cb)
			printf("VICTORY");
		else
			printf("DEFEAT");
		return 0;
	}
	else
	{
		if (ca >= cb - 1)
			printf("VICTORY");
		else
			printf("DEFEAT");
		return 0;
	}

}