[Python] 24553번 팰린드롬 게임 / 31648번 Palindrome Game

 

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

24553번: 팰린드롬 게임

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

31648번: Palindrome Game

---

 

24/03/23 / 24/03/25

 

 

실질적으로 같은 코드로 풀리는 문제이다. 간단한 게임이론 문제다.

---

 

문제 접근 방식:

 

 

처음 접근 방식은 $100$까지만 간단하게 문제에서 요구하는 승패 여부를 게임 DP를 사용하여 구했다.

 

규칙은 $10$의 배수일 때 후공이 이기고, 그렇지 않은 경우에 선공이 이기는 규칙이었다.

 

이 규칙의 정당성 증명은 다음과 같다.

 

한 자리 수는 모두 팰린드롬 수이므로, 이 경우 선공이 항상 이긴다.

 

$10$의 경우 후공이 이긴다.

 

$11$부터 $19$까지는 모두 선공이 한 자리 수 팰린드롬 만큼 돌을 가져감으로써 후공이 이기는 상태로 넘길 수 있다.

 

$10$의 배수들은 절대 팰린드롬 수가 아니다. 따라서 선공이 첫 턴에 모든 돌을 가져가서 후공이 지는 일은 발생하지 않는다.

 

지금까지의 $10$의 배수들은 모두 후공이 이겼는데, 어떤 특정한 $10$의 배수가 될 때 선공이 이긴다고 가정하자. 그 말은 곧, 그 수에서 적당히 팰린드롬 수 만큼의 돌을 빼서 후공이 이기는 상태로 넘길 수 있다는 말이다.

 

그러면 빼는 수 또한 $10$의 배수여야하고, $10$의 배수는 팰린드롬 수가 아니기 때문에 모순이 발생한다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 24553번 팰린드롬 게임
# 게임 이론
'''
접근 방법:
DP로 규칙 찾기
'''
'''
DP = [0 for _ in range(101)]
DP[0] = 1
palin = []
def is_palin(word):
    for i in range(len(word) // 2):
        if word[i] != word[-1 - i]:
            return False
    return True
for i in range(1, 101):
    if is_palin(str(i)):
        palin.append(i)

for i in range(1, 101):
    for p in palin:
        if i-p >= 0 and DP[i-p] == 1:
            break
    else:
        DP[i] = 1
'''
import sys
input = sys.stdin.readline
ans = []
for _ in range(int(input())):
    ans.append(int(not bool(int(input())%10)))
print(*ans, sep='\n')

# 31648번 Palindrome Game
# 게임 이론
import sys
input = sys.stdin.readline
ans = []
for _ in range(int(input())):
    if input().rstrip()[-1] == '0':
        ans.append('E')
    else:
        ans.append('B')
print(*ans, sep='\n')