사용자 도구

사이트 도구


ps:problems:boj:34130

Yet Another Stone Game

ps
링크acmicpc.net/…
출처BOJ
문제 번호34130
문제명Yet Another Stone Game
레벨플래티넘 3
분류

게임 이론

시간복잡도O(T*n)
인풋사이즈T*n <= 300000
사용한 언어Python 3.13
제출기록66624KB / 220ms
최고기록220ms
해결날짜2025/08/21

풀이

  • 가능한 상태들을 잘 분류해서 승리 전략을 하나씩 따져보면 되긴 하는데 간단하지는 않다.
  • 돌이 홀수개인 돌더미를 홀수더미, 돌이 짝수개인 돌더미를 짝수더미라고 하자.
  • 우선 당연히 돌이 하나도 없으면 패배 포지션이다.
  • A) 모든 더미가 짝수더미이면 패배 포지션이다.
    • 내가 몇개의 더미를 골라 돌을 제거하면, 다음턴에 상대방도 똑같은 더미를 골라서 돌을 제거하는 것이 가능하다. 이것을 반복하면 결국 돌이 하나도 없는 상태가 나에게 돌아온다.
  • B) 홀수더미가 1개 이상 K개 이하라면 승리 포지션이다
    • 홀수더미들을 모두 골라서 돌을 제거하면, 모든 더미가 짝수더미인 상태로 만들 수 있다.
  • 여기까지는 쉽게 해결이 된다. 이제 해결해야 하는 것은 홀수더미가 K보다 많은 경우인데, 다행히 K⇐N-2라는 조건이 있기때문에 경우의 수가 아래의 3가지로 한정된다.
  • C) 홀수더미가 K개보다 많은 경우.
    • C-1) K == N-1 이고, 홀수더미가 N(=K+1)개인 경우는 패배 포지션이다.
      • 어떤 더미들을 골라서 제거하든, 홀수더미가 K개 이하로 남게 된다.
    • C-2) K == N-2 이고, 홀수더미가 N-1(=K+1)개, 짝수더미가 1개인 경우
      • 이 경우가 제일 복잡하다. 홀수더미를 K개보다 많도록 유지하는 방법이 두가지 있다. 짝수더미에서만 제거하기와, 짝수더미와 홀수더미 하나를 골라서 제거하기.
      • 홀수더미중에 돌이 1개만 있는 더미가 있다면 승리 포지션이다.
        • 돌이 1개만 있는 더미와 짝수더미를 골라서 하나씩 제거한다. 이렇게 되면 홀수더미만 K+1개가 남게 된다. 이것은 위의 1번 포지션이다.
      • 모든 홀수더미에 돌이 3개 이상이고, 짝수더미에 돌이 2개라면 패배 포지션.
        • 짝수더미에서만 돌을 제거하면, 상대방은 다음차례에 다시 그 더미에서만 돌을 제거해서 홀수더미 K+1개가 되게 만든다.
        • 짝수더미와 홀수더미 한개에서 돌을 제거하면, 상대방은 역시 똑같은 더미들에서 돌을 제거해서 홀수더미 K+1개가 되게 만든다.
      • C-2-1)가장 돌의 개수가 적은 더미가 짝수더미이면 패배포지션
        • 위와 동일. 짝수더미에서만 돌을 제거하든 짝수더미와 홀수더미 한개에서 돌을 제거하든, 상대방은 똑같은 더미에서 돌을 제거하면, 짝수더미가 1개뿐이고 그게 돌의 개수가 가장 적은 상태로 되돌아온다. 계속 반복하면, 짝수더미에 돌이 2개인 상태가 된다.
      • C-2-2)가장 돌의 개수가 적은 더미가 홀수 더미라면 승리포지션.
        • 돌의 개수가 가장 적은 더미와, 짝수더미에서 돌을 제거하면, 가장 돌의 개수가 적은 더미가 짝수더미인 상태로 만들수 있다.
    • C-3) K == N-2 이고, 홀수더미가 N(=K+2)개인 경우.
      • 가장 돌의 개수가 적은 더미 한개를 골라서 돌을 제거하면 (C-2-1)번 상태로 만들 수 있다.

코드

"""Solution code for "BOJ 34130. Yet Another Stone Game".

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

Tags: [game theory]
"""

import sys
from teflib import psutils


@psutils.run_n_times
def main():
    N, K = [int(x) for x in sys.stdin.readline().split()]
    a = [int(x) for x in sys.stdin.readline().split()]

    odd_count = sum(1 for a_i in a if a_i % 2 == 1)
    if K == 1:
        print('First' if sum(a) % 2 == 1 else 'Second')
    elif odd_count == 0:
        print('Second')
    elif odd_count <= K:
        print('First')
    elif odd_count == N == K + 1:
        print('Second')
    elif odd_count + 1 == N == K + 2:
        print('Second' if min(a) % 2 == 0 else 'First')
    elif odd_count == N == K + 2:
        print('First')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
J​ D Y P M
 
ps/problems/boj/34130.txt · 마지막으로 수정됨: 2025/08/21 06:44 저자 teferi