사용자 도구

사이트 도구


ps:problems:boj:32908

Programmers and Stones

ps
링크acmicpc.net/…
출처BOJ
문제 번호32908
문제명Programmers and Stones
레벨골드 3
분류

게임 이론

시간복잡도O(n)
인풋사이즈n<=100000
사용한 언어Python 3.13
제출기록44748KB / 64ms
최고기록64ms
해결날짜2025/01/17

풀이

  • 모든 포지션을 두 가지 그룹으로 나눠서 풀 수 있는 게임이론 문제
  • 모든 포지션을 '모든 파일에 돌이 짝수개인 포지션' 와 '돌이 홀수개 있는 파일이 존재하는 포지션' 으로 나누자.
  • 최종적으로 패배하게 되는 포지션인 '모든 파일에 돌이 하나도 없는 포지션'은 '모든 파일에 돌이 짝수개인 포지션' 에 포함된다
  • '모든 파일에 돌이 짝수개인 포지션' 에서는 어떤 액션을 취해도 '돌이 홀수개 있는 파일이 존재하는 포지션'으로 전환된다
  • '돌이 홀수개 있는 파일이 존재하는 포지션' 에서는 항상 '모든 파일에 돌이 짝수개인 포지션'으로 전환시키는 액션이 존재한다
  • 따라서, '모든 파일에 돌이 짝수개인 포지션' 이 패배포지션, '돌이 홀수개 있는 파일이 존재하는 포지션'이 승리포지션이다.

코드

"""Solution code for "BOJ 32908. Programmers and Stones".

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

Tags: [game theory]
"""


def main():
    n = int(input())  # pylint: disable=unused-variable
    a = [int(x) for x in input().split()]
    print('Dmitry' if all(x % 2 == 0 for x in a) else 'Alice')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
P A X Q S
 
ps/problems/boj/32908.txt · 마지막으로 수정됨: 2025/01/29 08:48 저자 teferi