[boj : 11565] 바이너리 게임

www.acmicpc.net/problem/11565

11565번: 바이너리 게임

문제 : 문자열 a,b가 주어지고 a를 b로 만들 수 있는가?를 묻고 있음.

규칙 1 : 맨 앞문자를 지울 수 있음

규칙 2 : 맨 뒤에 문자를 추가할 수 있음. 이때 1이 홀수개이면 1을 나머지는 0을 추가

 

해설 : 와,,,이런문제 너무 싫어요....근데 또 재밌어 ㅋㅋㅋ(전형적으로 codeforces 에서 나올 법한 문제)

문제에 말리면 절대 풀 수 없는 문제.

결론부터 말하면 a와 b가 어떻게 생겨먹었든 전혀 상관 없다. 즉, '모양'과는 아무런 상관이 없다.

 

하나씩 생각해보면 1을 추가하려면 1이 홀수개가 존재야하고 추가를 하는 순간 짝수개가 된다. 그러면 맨앞의 문자들을 지워서 1을 다시 홀수개로 만들지 못한다면 0밖에 추가를 못한다.

 

이거를 다시 풀어보면 1을 추가할 수 있는 개수는 단 한개뿐! 이라는 것이다.

(종이에 적어보면서 하나씩 추가해보고 지워봐라)

 

저게 이해가 되면 문제는 쉽게 풀린다.

a문자열이 원래 홀수였다면 1을 1개 늘릴 수 있다.

a문자열이 원래 짝수였다면 1을 전혀 늘리지 못한다.

 

이걸 캐치했다면 코드로 옮기는 것만 남았다.

#include<bits/stdc++.h>

using namespace std;

int main()
{
	string x, y;
	cin >> x >> y;

	int a = 0, b = 0;
	for (int i = 0; i < x.length(); i++)
		if (x[i] == '1')a++;
	for (int j = 0; j < y.length(); j++)
		if (y[j] == '1')b++;
	a = (a + 1) / 2;
	b = (b + 1) / 2;
	cout << ((a >= b) ? "VICTORY" : "DEFEAT");
	return 0;
}