[BOJ 24553] 백준 24553번 - 팰린드롬 게임

February 27, 2022

		2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 풀이
A		[BOJ 24542] 튜터-튜티 관계의 수
C		[BOJ 24544] 카카오뷰 큐레이팅 효용성 분석
D		[BOJ 24545] Y
G		[BOJ 24548] 도로 정보
K		[BOJ 24552] 올바른 괄호
L		[BOJ 24553] 팰린드롬 게임

1. 문제

백준 24553번 - 팰린드롬 게임 (https://www.acmicpc.net/problem/24553)

돌 가져가기 문제의 기본 베이스는 현재 상황에서 어떠한 행동을 취하더라도 상대가 이기는 경우가 나온다면, 그 시점에서 시작한 플레이어는 패배하는 것이다.

반대로, 상대가 지는 경우가 단 하나라도 있다면, 그 길을 선택해서 승리할 수 있다.

팰린드롬 수는 $1, 2, 3, …$ $\,, 9, 11, 22, 33, …$ $\,, 99, …$ 가 있다.

$N=1\sim 9$인 경우, 전부 가져가면 돼서 시작하는 사람이 승리한다.

$N=10$인 경우, $1\sim 9$중 몇 개를 가져가더라도 시작하는 사람이 이기는 개수만큼 남는다. 따라서 패배한다.

$N=11\sim 19$인 경우, $1\sim 9, 11$중에 그만큼 가져가서 시작하는 사람이 지는 개수만큼 남게 할 수 있다. 따라서 승리한다.

$N=20$인 경우, $1\sim 9, 11$중 몇 개를 가져가더라도 시작하는 사람이 이기는 개수만큼 남는다. 따라서 패배한다.

위와 같이 계속 반복되며 동일한 주기를 갖는다. 따라서 $N$이 $10$의 배수이면 승우가 이기고, 아니면 상윤이 이긴다.