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()
ps/problems/boj/34130.txt · 마지막으로 수정됨: 2025/08/21 06:44 저자 teferi
토론