[백준 24553번] 팰린드롬 게임 C++ 풀이

1. 문제 

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

24553번: 팰린드롬 게임

$N$개의 돌을 가지고 게임을 한다.

게임의 룰은

     1. 상윤이가 롤을 먼저 가져가는 것으로 게임이 시작된다.

     2. 자신의 차례에 팰린드롬 수(대칭인 수 ex)1,33,535) $x$를 가져 갈 수 있다.

     3. 돌을 가져갈 수 없다면 패배한다. (마지막 돌을 가져가는 사람이 승리한다)

     4. 두사람은 모두 최선의 선택을 한다.

 

 

2. 접근

문제를 보자마자 돌게임 문제를 풀어 봤다면 dp에 의한 접근 방법을 생각해 볼 수 있다.

게임이론에 대해 처음 접하는 경우 아래 문제를 먼저 푸는 것을 추천한다.

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

9655번: 돌 게임

그러나 문제는 돌의 개수가 $ 1\leq n\leq 10^{19}$ 으로 dp로 하는경우 최대으로 dp로 구현하는 경우, 시간복잡도가 $O(N^2)$ 으로 시간초과이다.

O(N)에도 시간이 부족하기 때문에 테스트 케이스 $1\leq T \leq 1000$이라는 점에서 모든 숫자를 전부 계산 해볼 필요 없이 다른 방법이 존재한다는 것을 알 수 있다.

일단 직접 게임 결과를 써봤다.

1	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	1

0은 상윤이가 이기는 경우 1은 승우가 이기는 경우이다.

1~9는 모두 팰린드롬 숫자 이므로 상윤이 돌을 모두 가져갈수 있어 상윤이가 승리한다(0).

10의 경우 상윤이가 어떤 숫자를 가져가더라도 9개 이하의 돌이 남아 승우가 남은 돌을 모두 가져가는 경우가 반드시 존재하기 때문에 승우가 승리한다(1).

여기까지가 기본적인 게임이론 접근이다. 

계속 해보자

11	12	13	14	15	16	17	18	19	20
0	0	0	0	0	0	0	0	0	1

 11~19에서는 상윤이는 반드시 10개의 돌을 남기고 가져가는 경우가 존재한다.(일의 자리 숫자가 모두 팰린드롬 숫자이기 때문에) 따라서 10개가 남은 돌은 받은 승우는 N=10에서 상윤이가 패배하는 것 처럼 반드시 패배하는 경우가 발생하여 패배하게 된다.

여기서 10과 20와 같이 10의 배수의 경우에만 승우가 이기고 나머지는 상윤이가 이긴다는 것이 확인되었고, 21~30 ,,,91_100도 동일한 결과가 나온다는 것을 확인할 수 있다.

 

그러면 100이상에도 동일한 규칙이 적용되는가?

$\Rightarrow $결론부터 이야기하면 그렇다. 

다만 숫자가 커지는 경우 가져갈 수 있는 팰린드롬 수가 일의자리 뿐만 아니라 121,14141와 같이 2자리 수 이상의 팰린드롬 수에 의해 예외가 발생할 수 도 있지 않을까라는 생각이 들 수도 있는데, 만약이 예외가 발생하는 경우

1. N=10의 배수 $a$에서 팰린드롬 수$p$를 빼서 해당 값이 1을 가지는 index $b$에 도달할 수 있으면 승우가 반드시 패배하는 경우가 존재하게 되서 N이 $a$일때도 0을 가질 수 있는경우가 발생하게 되는데, 팰린드롬수는 10의 배수가 존재하지 않는다는 점에서 10의 배수에서 10의 배수가 아닌 수를 뺐을때 10의 배수를 절대 만들수 없게 되므로 존재하지 않는다.

2. N=10의 배수가 아닌경우 상윤이는 반드시 이기는 index가 존재하기 때문에 고려 할 필요가 없다.

 

주의 해야하는 경우가 있는데 N=팰린드롬 수 인 경우에는 10의 배수와 상관없이 상윤이가 이긴다.

 

3. 구현

#include<iostream>
#include<vector>
using namespace std;
bool is_palindrome(long long num) {
	vector<long long>vec;
	long long temp;
	while (1) {
		temp = num % 10;
		vec.push_back(temp);
		num = num / 10;
		if (num == 0)
			break;
	}
	for (int i = 0; i < vec.size(); i++) {
		if (vec[i] != vec[vec.size() - 1 - i])
			return false;
	}
	return true;
}
int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	long long num;
	while (T--) {
		cin >> num;
		if (is_palindrome(num))
			cout << "0\n";
		else
			if (num % 10 == 0)
				cout << "1\n";
			else
				cout << "0\n";
	}


	return 0;
}