ps:problems:boj:29457
목차
Игра с графом
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 29457 |
문제명 | Игра с графом |
레벨 | 실버 4 |
분류 |
게임이론 |
시간복잡도 | O(1) |
사용한 언어 | Python 3.11 |
제출기록 | 31120KB / 40ms |
최고기록 | 40ms |
해결날짜 | 2024/02/02 |
풀이
- 그래프가 분리되지 않도록 하는 엣지들을 지워나가다가, 그것이 불가능해지면 진다.
- 어떤 엣지를 지워도 그래프가 분리되게 되는 것은 그래프가 트리가 되는 시점이고, 그때의 남은 엣지는 n-1개이다.
- 결국 서로 엣지를 1개씩 줄여나가다가, 자기 차례에 남은 엣지가 n-1개가 되는 사람이 지게 되는 것이므로, 처음 m-(n-1) 의 홀짝성에 따라 승리 플레이어가 결정된다. m-(n-1)이 홀수이면 선공 승리, 짝수이면 후공 승리이다. 실제 엣지가 어떻게 주어지는지는 볼 필요도 없다. 그래서 원래는 인풋 데이터를 읽는데만 O(m)이 걸리겠지만, 여기에서는 인풋 데이터를 다 읽을 필요조차 없다.
- 출력해야 하는 것은 승리하는 플레이어가 아니라 패배하는 플레이어라는 데에 주의하자
- 무승부가 나올 일이 없으므로, 무승부를 출력하는것은 페이크인가 싶은데.. 그런 경우가 있다. 처음에 노드가 1개밖에 없는, 그래서 당연히 엣지는 하나도 없는 경우이다. 사실 이 경우는, 문제에서 규칙이 명확하게 주어지지 않은거라서 결과가 무승부가 되는지 선공의 패배가 되는지가 불명확한 감이 있다. 하지만 이 경우에는 무승부로 출력해야 통과된다
코드
"""Solution code for "BOJ 29457. Игра с графом".
- Problem link: https://www.acmicpc.net/problem/29457
- Solution link: http://www.teferi.net/ps/problems/boj/29457
Tags: [game theory]
"""
def main():
n, m = [int(x) for x in input().split()]
if n == 1:
print('Draw')
else:
print('Alice' if (m - (n - 1)) % 2 == 0 else 'Bob')
if __name__ == '__main__':
main()
ps/problems/boj/29457.txt · 마지막으로 수정됨: 2024/02/02 12:57 저자 teferi
토론