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