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
                
                
토론