ps:problems:boj:16882
카드 게임
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 16882 |
문제명 | 카드 게임 |
레벨 | 골드 1 |
분류 |
게임 이론 |
시간복잡도 | O(n) |
인풋사이즈 | n<=10^5 |
사용한 언어 | Python 3.11 |
제출기록 | 43304KB / 96ms |
최고기록 | 80ms |
해결날짜 | 2023/06/17 |
풀이
- 가장 큰 숫자가 1개밖에 없으면, 그 숫자를 부름으로써 모든 카드를 제거할수 있다. 따라서 선공이 승리할 수 있다.
- 가장 큰 숫자가 홀수개 있더라도, 가장 큰 숫자를 불러서 가장 큰 숫자만 짝수개 남길수 있다. 이후, 서로 그 숫자를 부르는 것을 반복하면 마지막에 숫자를 부르는 것은 선공의 차례가 된다. 역시 선공의 승리.
- 가장 큰 숫자가 짝수개 있으면, 그 숫자를 먼저 부르는 사람이 지는 게임이 된다. 만약 두번째로 큰 숫자가 1개밖에 없다면, 선공은 그 숫자를 불러서 가장 큰 숫자만 남기고 나머지를 모두 지울수 있다. 선공의 승리.
- 두번째로 큰 숫자가 홀수개 있더라도, 그 숫자를 불러서 가장 큰 숫자를 상대방이 먼저 부르게 강요시킬수 있다. 선공의 승리.
- 두번째로 큰 숫자도 짝수개 있으면, 두번째로 큰 숫자를 먼저 부르는 사람이 가장 큰 숫자도 먼저 부르게 되고 결국 게임을 지게 된다. 세번째로 큰 숫자가 홀수개 있으면 똑같은 전략으로 선공은 상대방이 두번째로 큰 숫자를 먼저 부르도록 강요할수 있다.
- 이것을 반복하면.. 선공의 필승 전략은 갯수가 홀수개인 숫자들중에서 가장 큰 숫자를 부르는 것이다. 그리고 선공에게 필승 전략이 없는 경우는 모든 숫자가 짝수개 있는 경우로, 이 경우에는 후공이 승리한다
- 이제 모든 숫자가 짝수개 있는지만 체크하면 되므로, O(n)에 계산 가능하다.
코드
"""Solution code for "BOJ 16882. 카드 게임".
- Problem link: https://www.acmicpc.net/problem/16882
- Solution link: http://www.teferi.net/ps/problems/boj/16882
Tags: [game theory]
"""
import collections
def main():
N = int(input()) # pylint: disable=unused-variable
A = [int(x) for x in input().split()]
is_win_pos = any(x % 2 == 1 for x in collections.Counter(A).values())
print('koosaga' if is_win_pos else 'cubelover')
if __name__ == '__main__':
main()
ps/problems/boj/16882.txt · 마지막으로 수정됨: 2023/06/17 15:51 저자 teferi
토론