사용자 도구

사이트 도구


ps:problems:boj:24678

돌무더기 게임 1

ps
링크acmicpc.net/…
출처BOJ
문제 번호24678
문제명돌무더기 게임 1
레벨골드 3
분류

게임 이론

시간복잡도O(t)
인풋사이즈t<=200,000
사용한 언어Python 3.11
제출기록31256KB / 380ms
최고기록332ms
해결날짜2023/06/13

풀이

  • 어떤 돌무더기를 골라서 돌을 빼고 더하든, 공통적으로 돌무더기 세개의 홀짝성을 모두 바꾸게 된다.
  • 이 말을 바꾸면, 내 차례에 돌이 홀수개 있는 무더기의 갯수가 0개 또는 1개 였다면, 상대방 차례에는 돌이 홀수개 있는 무더기의 갯수가 2개 또는 3개가 된다.
  • 이 게임에서 승리하는 상황은, 비어있는 돌 무더기가 2개 이상이 되는 경우이고, 이때는 돌이 홀수개 있는 무더기의 갯수가 0개 또는 1개이다.
  • 처음 시작할때, 돌이 홀수개 있는 무더기의 갯수가 2개 또는 3개였으면, 어떤 과정을 거치더라도 비어있는 돌 무더기가 2개 이상이 되는 상태로는 도달할수 없다. 반대로 돌이 홀수개 있는 무더기의 갯수가 0개 또는 1개였다면, 어떤 과정을 거치더라도 최종적으로 저 상태에 도달한다.
  • 따라서 주어진 포지션이 승리포지션인지 확인하는 것은 돌이 홀수개 있는 무더기의 갯수만 세어주면 되므로 O(1)에 처리가능.

코드

"""Solution code for "BOJ 24678. 돌무더기 게임 1".

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

Tags: [game theory]
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        x, y, z = [int(x) for x in sys.stdin.readline().split()]
        is_win_pos = x % 2 + y % 2 + z % 2 <= 1
        print('R' if is_win_pos else 'B')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
I A B G U
 
ps/problems/boj/24678.txt · 마지막으로 수정됨: 2023/06/16 06:07 저자 teferi