[Python] 19891번 Занимательное дежурство

 

 

https://www.acmicpc.net/problem/19891

---

 

24/05/26

 

 

푼 사람이 매우 적은 게임 이론 문제이다. 기록으로 남겨두면 좋을 것 같아서 작성해본다.

---

 

문제 접근 방식:

 

 

문제 해석은 다음과 같다.

 

어느 날 쉬는 시간에 수업 시간에 디마는 칠판에 라틴어 글자를 몇 개 써놓고 그리샤를 불러서 보라고 했습니다.
그리샤는 칠판의 구성이 정말 마음에 들었지만 수업이 시작될 때까지 칠판은 완벽하게 깨끗해야 했습니다.
아이들은 글자를 그냥 지우는 것이 안타까웠고, 이 과정을 더 재미있게 만들기 위해 그리샤는 재미있는 게임을 제안했습니다. 남자들이 돌아가면서 움직입니다.
자신의 차례에 플레이어는 보드에서 두 개의 동일한 글자를 지우고 그 대신 보드에 어떤 종류의 글자든 한 글자를 씁니다.
예를 들어 $\{a, b, a\}$ 문자 집합에서 $\{a, b\}, \{b, b\}, \{b, c\}, \cdots,\{b, z\}$ 집합을 얻을 수 있습니다.
보드에 쓰여진 글자가 모두 다르기 때문에 한 칸도 움직일 수 없는 사람이 패자가 됩니다. 패자는 판을 씻습니다.
그리샤가 먼저 움직입니다. 엄격한 선생님 다리아 블라디미로브나가 주의 깊게 지켜보고 있습니다.
그녀는 두 플레이어가 최적의 전략를 고수한다면 아이들이 발명 한 게임에서 누가 이길 것인지 알고 싶어합니다.
당신의 임무는 그녀가 이 질문에 대한 답을 찾도록 돕는 것입니다.
입력 파일의 한 줄에는 원래 보드에 쓰여진 문자 세트가 포함됩니다. (세트의 문자 수는 1~10만 개이며 문자는 공백으로 구분되지 않습니다).
출력 파일에서 그리샤가 이기면 그리샤를, 그렇지 않으면 디마를 인쇄합니다.

 

처음에 나이브하게 생각했던 건 그냥 게임 DP이다.

 

어차피 문자들이 뒤섞여있든 정렬되어있든, 같은 문자 두 개를 골라 없애고 다시 하나를 써 넣는 행위를 반복하므로, 모든 게임판이 정렬되어 있다고 간주했다.

 

이를 통해 게임 DP를 직접 구현하려고 했으나, 한 플레이어가 할 수 있는 행동이 너무 많았다.

 

예를 들어, $\{a, a, b\}$에서 만들 수 있는 게임판은 $\{b, a\}$부터 $\{b, z\}$까지 알파벳 개수인 $26$개이다.

 

즉, 같은 문자 두 개를 골라 없애고 다시 하나를 써 넣을 때 써 넣을 수 있는 문자의 종류가 $26$개라서, 이 모든 상황을 DP로 저장한다면 분명 메모리 초과, 시간 초과가 날 것 같았다.

 

따라서, 분명 다른 방법이 있을 것이라 생각했다.

 

이틀 정도 고민을 하고 다양한 게임판을 직접 손으로 그려서 따라가 봤지만, 규칙이 잘 보이지 않았다.

 

이 문제를 해결하신 다른 분(jh01533님)에게 힌트를 받았고, 그 분께서 아주 중요한 힌트를 하나 던져주어서 해결할 수 있었다.

 

힌트

해답은 게임판을 맨 처음 내가 나이브하게 생각했던 것처럼 다양한 문자들의 집합으로 보면 안된다는 것, 그러기 때문에 다른 방법으로 게임판을 "치환"시켜야하고, 그 방법이 (쌍의 개수, 낱개의 개수)로 게임판을 바라보는 관점이라는 것이다.

 

결국 문자의 쌍을 하나 없애고, 다시 하나 써 넣는 것의 반복이기 때문에 어떤 문자를 사용하든 간에 별 상관이 없다.

 

이 관점으로 $a, a, b$를 보면, $(1, 1)$로 치환이 된다. $a, a, b, b, c, c$라면, $(3, 0)$으로 치환될 것이다.

 

일반적으로 어떤 행동을 하면 다음과 같이 둘 중 하나로 갈린다.

 

1. 쌍을 하나 없애고, 아직 낱개가 존재하지 않는 문자를 하나 써 넣기.

2. 쌍을 하나 없애고, 기존에 낱개가 존재하는 문자를 하나 써 넣기.

 

1번의 경우, 쌍의 개수가 하나 줄어듦과 동시에 낱개 문자가 하나 늘어난다.

2번의 경우, 쌍의 개수가 하나 줄어듦과 동시에 낱개 문자가 하나 줄어들고, 쌍의 개수가 하나 늘어난다. 즉, 낱개 문자가 하나 줄어드는 것과 같다.

 

$a, a, b$의 예시를 보면, $a, a$를 없애고 $b$를 써넣을 수도 있고, $b$이외의 문자를 써넣을 수도 있다.

 

전자는 2번, 후자는 1번 행동에 속한다고 볼 수 있다.

 

문자가 최대 $10$만자라고 했으므로, 쌍의 개수는 최대 $50,000$개, 그리고 낱개의 개수는 알파벳 개수와 동일한, 최대 $26$개이므로, 충분히 2차원 DP를 돌릴 수 있다!

 

나의 경우 저 1번 경우와 2번 경우가 된다는 걸 머릿 속으로 떠올린 후, 곧바로 손으로 직접 풀기 시작했다.

 

DP

행은 쌍의 개수, 열은 낱개의 개수이다.

 

이때, 낱개가 26개라면, 즉, 모든 문자가 적어도 하나씩 존재하면, 있는 문자를 써 넣을 수 밖에 없으므로 2번 행동밖에 할 수 없다.

 

마찬가지로 낱개가 0개라면 1번 행동 밖에 할 수 없다.

 

DP도 규칙을 발견할 수 있는데, 쌍의 개수가 0개거나 낱개의 개수가 26개면 무조건 선공이 지는 포지션이고, 그 외에도 쌍이 2개 이상 존재하는 데, 낱개의 개수가 짝수개가 존재한다면 선공이 지는 포지션이 된다.

 

이를 그대로 케이스워크로 구현해주면 끝이다. 간만에 재미있는 게임 이론 문제를 해결한 것 같아서 좋다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 19891번 Занимательное дежурство
# 게임 이론
'''
문제 해석:
어느 날 쉬는 시간에 수업 시간에 디마는 칠판에 라틴어 글자를 몇 개 써놓고 그리샤를 불러서 보라고 했습니다.
그리샤는 칠판의 구성이 정말 마음에 들었지만 수업이 시작될 때까지 칠판은 완벽하게 깨끗해야 했습니다.
아이들은 글자를 그냥 지우는 것이 안타까웠고, 이 과정을 더 재미있게 만들기 위해 그리샤는 재미있는 게임을 제안했습니다.

남자들이 돌아가면서 움직입니다.
자신의 차례에 플레이어는 보드에서 두 개의 동일한 글자를 지우고 그 대신 보드에 어떤 종류의 글자든 한 글자를 씁니다.
예를 들어 {a, b, a} 문자 집합에서 {a, b}, {b, b}, {b, c}, ...,{b, z} 집합을 얻을 수 있습니다.
보드에 쓰여진 글자가 모두 다르기 때문에 한 칸도 움직일 수 없는 사람이 패자가 됩니다.
패자는 판을 씻습니다. 그리샤가 먼저 움직입니다.

엄격한 선생님 다리아 블라디미로브나가 주의 깊게 지켜보고 있습니다.
그녀는 두 플레이어가 최적의 전략를 고수한다면 아이들이 발명 한 게임에서 누가 이길 것인지 알고 싶어합니다.

당신의 임무는 그녀가 이 질문에 대한 답을 찾도록 돕는 것입니다.

입력 파일의 한 줄에는 원래 보드에 쓰여진 문자 세트가 포함됩니다.
(세트의 문자 수는 1~10만 개이며 문자는 공백으로 구분되지 않습니다).

출력 파일에서 그리샤가 이기면 그리샤를, 그렇지 않으면 디마를 인쇄합니다.

접근 방법:

'''
import sys
input = sys.stdin.readline
S = input().rstrip()

pair, single = 0, 0
dummy = [0 for _ in range(26)]
for char in S:
    dummy[ord(char)-ord('a')] += 1
for i in range(26):
    pair += dummy[i]//2
    single += dummy[i]%2
if pair == 0 or single == 26 or (pair > 1 and single % 2 == 0):
    print('Dima')
else:
    print('Grisha')