돌 무더기에서 팰린드롬(palindrome)인 정수 개수만큼 가져갈 때 이기는 방법

31648번: Palindrome Game (acmicpc.net)

 

 

 

돌 무더기에 s개의 돌이 있는데, A,B가 양의 정수 x개만큼 돌을 가져간다.

 

여기서 x는 palindrome이어야 한다. 

 

palindrome은 앞에서 읽어도 뒤에서 읽어도 같은 수이다.

 

예를 들어 1, 121, 9009는 palindrome이다.

 

앞에 0을 붙이는 것은 허용하지 않는다. 예를 들어 990은 palindrome이 아니다.

 

s가 주어질때, 최선을 다해 게임하는 둘에 대해 선공이 이기는지 후공이 이기는지 판단

 

--------------------------------------------------------------------------------------------------------------------------------------------

 

1부터 9까지 한자리 수는 반드시 palindrome이다.

 

따라서, s가 1~9라면 선공이 반드시 이긴다.

 

마찬가지 이유로, 처음 주어진 수가 palindrome이면 선공이 반드시 이긴다.

 

앞에 0을 붙이는 것은 허용하지 않기 때문에 뒤에 0이 붙은 10의 배수는 절대로 palindrom이 아니다.

 

10의 배수가 아닌 2자리 이상의 어떤 수 s가 주어질 때,

 

선공이 1~9중 하나를 가져가 반드시 일의 자리를 0으로 만들 수 있다.

 

 

즉, 매 턴마다 선공은 반드시 10의 배수 형태로 후공에게 넘겨줄 수 있다.

 

 

따라서 선공은 반드시 s = 10이 된 상태로 후공에게 넘겨줄 수 있으며

 

s = 10에서 돌무더기를 가져가는 사람은 이길 수 있는가?

 

 

1~9중 하나만 가져갈 수 있으므로, s = 10에서 돌무더기를 가져가는 사람은 1~9중 하나로 넘겨줘야하며,

 

따라서 그 다음 사람이 이기게 된다.

 

 

그러므로 s가 10의 배수이면 선공이 지게되며, 10의 배수가 아니면 선공이 반드시 이길 수 있다.

 

 

from sys import stdin

T = int(stdin.readline())

for _ in range(T):
    
    s = stdin.readline().rstrip()

    if s[-1] == '0':
        
        print('E')
    
    else:
        
        print('B')

 

 

s가 1 이상이라 10의 배수일 조건은 맨 뒷자리가 0이냐 아니냐이다.