[BOJ#24553] 팰린드롬 게임

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

1 초 (추가 시간 없음)

1024 MB (추가 메모리 없음)

630

405

349

62.770%

문제

상윤이와 승우는 통산전적 1000전 500승 500패, 영혼의 라이벌이다.

이들 중 누가 더 게임을 잘하는지 구별하기 위해 마지막 게임 한 판을 하기로 했다. 

게임의 룰은 다음과 같다. 

1.  �$N$개의 돌이 쌓여있는 돌 무더기에서 게임을 진행한다.  
2. 상윤이가 게임을 먼저 시작한다. 그 후에 승우, 상윤이 번갈아가면서 게임을 진행한다.
3. 자신의 차례가 오면, 돌 무더기에서 돌을 �$x$개 가져오는 행동을 할 수 있다. 이 때, �$x$는 팰린드롬 수여야 한다. 
4. 자신의 차례에 가져올 돌이 없다면 그 사람은 패배한다.

팰린드롬 수란 3$3$, 11$11$, 929$929$ 와 같이 뒤집어도 같은 수가 나오는 양의 정수를 의미한다. 010$010$ 와 같이 의미 없는 0$0$이 앞에 있는 경우는 포함하지 않는다. 

상윤이와 승우 모두 1000판의 게임을 해온 고수들이라 항상 최선의 수만을 둔다. 

돌의 개수 �$N$이 주어졌을 때, 누가 이기는지 출력한다. 

입력

첫째 줄에 테스트 케이스의 개수 �$T$가 주어진다. (1≤�≤1000$1 \le T \le 1\,000$)

둘째 줄부터 �$T$개의 줄에 걸쳐, 돌 무더기에 쌓여 있는 돌의 개수 �$N$이 주어진다. (1≤�≤1018$1 \le N \le 10^{18}$)

출력

각 게임에서 상윤이가 이긴다면 0, 승우가 이긴다면 1을 출력한다.

---

제출 코드

T = int(input())
for tc in range(T):
    num = int(input())
    if num % 10 == 0:
        print(1)
    else:
        print(0)

 

초고수들의 게임이기에 처음 10의 단위수를 만나는 경우를 제외하고는 먼저 시작하는 쪽이 유리하다.

선공으로 끝자리 수가 0이 되게 만든다면, 팰린드롭 수는 끝자리가 0이 될 수 없기때문에

어떤 팰린드롭 수의 돌을 가져가도 무조건 돌이 남기 때문이다.

 

로직이 재밌었던 문제. 발상은 어려웠는데 구현은 매우쉬웠다.