[BOJ 7787 // C++] 빨간 칩, 초록 칩

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

 

이번에 볼 문제는 백준 7787번 문제인 빨간 칩, 초록 칩이다.
문제는 아래 링크를 확인하자.

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

7787번: 빨간 칩, 초록 칩

각 색의 칩에 대하여 칩의 개수 별 grundy number을 구해보자.

 

어떤 수 $x$가 홀수이고, 이 수 이하의 모든 양의 짝수(0이 제외되어있음에 유의하자)의 grundy number가 모두 2 이상이라고 가정해보자. 이 때 $x$에서 자기자신이 아닌 약수를 빼면 항상 짝수가 나오고, 해당 수의 grundy number는 모두 2 이상이 되므로 $x$의 grundy number 또한 1이 됨을 알 수 있다.

 

반대로 어떤 수 $x$가 짝수이고, 이 수 이하의 모든 양의 홀수의 grundy number가 모두 1이라고 가정해보자. 이 때 $x$에서 자신의 약수중 하나인 1을 빼면 항상 홀수가 나오고, 해당 수의 grundy number는 가정에 따라 1이므로 $x$의 grundy number은 2 이상이 됨을 알 수 있다.

 

위의 내용과 적은 칩 개수에 대한 초기값을 이용하면, 항상 홀수의 grundy number는 1, 짝수(0 제외)의 grundy number는 2 이상이 됨을 알 수 있다.

 

지금까지의 과정을 각 수가 가지고 있는 소인수 2의 개수에 대해 반복하면 각 양의 정수의 grundy number는 (그 수가 가지고 있는 소인수 2의 개수) + 1이 됨을 알 수 있다.

 

각 색의 칩의 개수의 grundy number와 Sprague-Grundy 정리를 이용해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int r, g;
int R = 1, G = 1;

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

	cin >> r >> g;
	while ((r & 1) == 0) R++, r >>= 1;
	while ((g & 1) == 0) G++, g >>= 1;

	if (R ^ G) cout << "A player wins";
	else cout << "B player wins";
}