ps:problems:boj:18580
Long Game
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 18580 |
| 문제명 | Long Game |
| 레벨 | 골드 1 |
| 분류 |
게임 이론 |
| 시간복잡도 | O(n) |
| 인풋사이즈 | n<=10^5 |
| 사용한 언어 | Python 3.11 |
| 제출기록 | 42172KB / 72ms |
| 최고기록 | 72ms |
| 해결날짜 | 2023/07/15 |
풀이
- 복잡하게 생각할것이 없다. 인접한 페어들 중에서 인버전이 있는것들만 생각해보자. 그 페어들이 모두 끊어지면 인버전은 하나도 남지 않는다.
- 그러면 어떤식으로든 서로 게임을 진행하다가 인버전 페어가 한개만 남는다면 그 페어를 끊는 순간 지기 때문에, 둘다 그곳을 제외한 남은곳들을 자를것이다. 그리고 남은 곳이 인버전페어 한군데만 남게 될때 그곳을 자르고 지게 된다. 결국, 마지막 턴을 진행하는 사람이 지게 된다.
- 끈의 길이가 홀수면, 자를 곳은 짝수개이고 마지막 턴은 bob에게 돌아오게 된다. 승자는 alice. 반대로 끈의 길이가 짝수면 승자는 bob.
- 예외처리가 필요한 곳은, 처음에 인버전이 하나도 없는 상태였다면 끈의 길이가 홀수든 짝수든 관계 없이 선공이 첫수에 자를 곳이 없으므로 bob이 이기게 된다. 이것을 처리하기 위해서 인버전이 존재하는지 여부를 O(n)에 확인해야 하고, 이것이 전체 시간복잡도가 된다
코드
ps/problems/boj/18580.txt · 마지막으로 수정됨: 2023/07/15 16:12 저자 teferi
토론