사용자 도구

사이트 도구


ps:problems:boj:34124

A의 배수

ps
링크acmicpc.net/…
출처BOJ
문제 번호34124
문제명A의 배수
레벨골드 2
분류

게임 이론

시간복잡도O(Q*1)
인풋사이즈Q<=10**6
사용한 언어Python 3.13
제출기록32412KB / 1084ms
최고기록972ms
해결날짜2025/08/16

풀이

  • 만약 아무 제약이 없다면, 매턴 1개씩 지울수 있으므로, N이 홀수면 선공의 승리, N이 짝수면 후공의 승리이다
  • 제약이 유효한 경우는, 마지막에 x와 Ax만이 남아있는 상태에서, 현재 턴 플레이어가 Ax를 지우는 경우 뿐이다. 하지만, 한 플레이어가 저 상황을 만들려고 아무리 노력해도 상대는 그렇게 남지 않도록 만드는 방법이 존재한다. 그러므로 제약이 없다면 패배하는 플레이어가 저 제약을 이용해서 승리하는 것은 불가능하다. 다만 그것이 가능한 유일한 경우는 A=N=2일 경우인데, 이때는 후공이 2를 지움으로써 승리하는 것이 가능하다. 그 경우만 예외처리해주면 끝.

코드

"""Solution code for "BOJ 34124. $A$의 배수".

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

Tags: [game theory]
"""

import sys


def main():
    Q = int(sys.stdin.readline())
    for _ in range(Q):
        N, A = [int(x) for x in sys.stdin.readline().split()]
        if N == A == 2:
            print('O')
        else:
            print('O' if N % 2 == 1 else 'I')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
O E​ T Y U
 
ps/problems/boj/34124.txt · 마지막으로 수정됨: 2025/08/21 06:54 저자 teferi