사용자 도구

사이트 도구


ps:problems:boj:24553

팰린드롬 게임

ps
링크acmicpc.net/…
출처BOJ
문제 번호24553
문제명팰린드롬 게임
레벨골드 4
분류

게임 이론

시간복잡도O(T)
인풋사이즈T<=1000
사용한 언어Python 3.11
제출기록31256KB / 44ms
최고기록40ms
해결날짜2023/06/12

풀이

  • 1~9까지는 모두 팰린드롬이다.
  • 일단 0은 패배포지션이고, 1~9는 0으로 이동이 가능하므로 승리포지션이다.
  • 여기서 좀더 나아가면, 현재 끝자리가 0이면 끝자리가 1~9인 수로만 이동이 가능하다. 0으로 끝나는 팰린드롬이 없기 때문이다. 반면, 현재 끝자리가 0이 아니면, 끝자리를 0인 수로 이동이 가능하다.
  • 그러므로, 끝자리가 0인 수는 모두 패배포지션. 끝자리가 0이 아닌수는 모두 승리포지션이다. 주어진 숫자의 끝자리가 0인지 아닌지만 확인하면 결과를 알수 있다.

코드

"""Solution code for "BOJ 24553. 팰린드롬 게임".

- Problem link: https://www.acmicpc.net/problem/24553
- Solution link: http://www.teferi.net/ps/problems/boj/24553

Tags: [game theory]
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N = int(sys.stdin.readline())
        print('0' if N % 10 != 0 else '1')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
G M D B X
 
ps/problems/boj/24553.txt · 마지막으로 수정됨: 2024/03/27 14:48 저자 teferi