김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 16882 카드 게임 파이썬(Python)

문제 링크

골드 2가 맞나 싶을 정도의 날먹 문제.
조금만 생각해보면 규칙을 쉽게 알 수 있다.
우선, 카드가 하나면 무조건 선공이 이긴다.
마찬가지 논리로, 모든 카드가 같은 숫자일 때(즉 카드 번호가 무의미할 때), 홀수 개면 선공이 이기고, 짝수 개면 후공이 이긴다.
예를 들어, 카드가 3장이면 선공이 이기고, 2장이면 후공이 이기는 것은 쉽게 알 수 있다.
이제 전체 게임 조건을 생각해보자, 카드를 고르면 그 카드보다 작은 카드는 모두 같이 없어지므로 가장 큰 카드부터 생각하면 간단하다는 것을 쉽게 알 수 있다.
가장 큰 카드가 홀수 개수면, 모든 카드가 같은 숫자인 것과 같은 게임이므로 선공이 무조건 이긴다. 선공이 가장 큰 카드 하나를 고르면 동시에 그 카드랑 같은 숫자를 제외한 모든 카드가 없어지기 때문이다.
예를 들어, 카드가 [1, 2, 2, 3, 3, 3]이라면 이는 [3, 3, 3]과 같은 케이스이다.
가장 큰 카드가 짝수 개수면 어떨까(예를 들어 [1, 2, 2, 3, 3])? 바로 알 수 있는 건 적어도 선공이 가장 큰 카드를 고르면 진다는 점이다. 모든 카드가 같은 숫자인 것과 동일한 케이스([3, 3])가 되기 때문이다.
그렇다면 선공 입장에서는 게임을 이기기 위해 가장 큰 카드가 아니라, 다른 카드를 골라야 한다.
이제, 예시의 게임 [1, 2, 2, 3, 3]을 [1, 2, 2]와 [3, 3]으로 분리해보자.
[3, 3]은 전술했듯 후공이 이기는 게임이고, [1, 2, 2]도 마찬가지 원리로 만약 선공이 가장 큰 수를 고른다면 후공이 이기는 게임이다.
후공이 이겼다면 선공의 차례에서 게임이 끝났다는 것인데, 이는 즉 [1, 2, 2]를 후공이 이겼다면, [3, 3]이 시작할 때 선공의 차례이므로 여전히 후공이 이긴다. 즉, [1, 2, 2, 3, 3]에서 선공이 2를 골라도 진다.
이제 [1, 2, 2]를 더 분리해보자. [1]과 [2, 2]로 분리할 수 있을 것이다.
[2, 2]는 전술했듯 후공이 이기는 게임이지만, [1]은 선공이 이기는 게임이다.
선공이 이겼다면 후공의 차례에서 게임이 끝났다는 것인데, 이는 즉 [2, 2]에서 원래 후공(cubelover)이 선공으로 게임을 시작해야 함을 의미한다.
즉, [2, 2]에서 선공과 후공이 뒤바뀌게 되므로 원래 선공(koosaga)이 이기는 게임이 된다.
[2, 2]에서 원래 선공이 이기면 이어지는 [3, 3]에서도 원래 선공이 이기므로 최종 승자는 원래 선공이 된다.
이러한 관찰에서, 우리는 한 가지 사실을 알 수 있다.

  1. 게임을 카드에 적힌 숫자별로 분리할 수 있다. 예를 들어 [1, 2, 2, 3, 3]은 [1], [2, 2], [3, 3]으로 분리할 수 있다.
  2. 카드가 홀수 개수인 게임은 선후공에 상관없이 원래 선공인 koosaga가 이긴다. 예를 들어, [1, 1, 2]는 [1, 1]과 [2]로 분리할 수 있지만, 선공 입장에선 굳이 1을 선택해서 [1, 1]을 진행할 필요 없이, 바로 2를 선택해서 이길 수 있다.
  3. 카드가 홀수 개수인 게임은 원래 선공인 koosaga를 후공으로, 원래 후공인 cubelover를 선공으로 만든다.
  4. 카드 개수가 짝수 개수인 게임은 현재 선공이 진다.
  5. 카드 개수가 짝수 개수인 게임은 선후공을 뒤바꾸지 않는다.

이 규칙을 정리하면, 카드 개수가 하나라도 홀수이면 무조건 koosaga가 이길 수 있다는 것을 의미한다. 카드 개수가 홀수인 판은 무조건 koosaga가 이기고, 나머지 짝수 판도 무조건 cubelover가 선공하기 때문에 koosaga가 이긴다.
cubelover가 이 게임에서 이기는 경우는, koosaga가 최적이 아닌 방법으로 게임을 하거나(이 문제의 가정과 맞지 않다), 모든 카드의 개수가 짝수여서 koosaga가 한번도 승기를 잡을 수 없는 경우밖에 없다.

#!python

n = int(input())
cards = map(int, input().split())
# cards_count[i]: i가 적힌 카드의 개수
cards_count = [0] * (10**5 + 1)
for card in cards:
    cards_count[card] += 1

# 홀수인 카드가 하나라도 있으면 선공 구사과 승
# 모든 카드가 짝수 개수면 후공 큐브러버 승
members = ["cubelover", "koosaga"]
print(members[any(count % 2 for count in cards_count)])

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑