사용자 도구

사이트 도구


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()

토론

댓글을 입력하세요:
W​ W I X S
 
ps/problems/boj/16882.txt · 마지막으로 수정됨: 2023/06/17 15:51 저자 teferi