[Python/BOJ] 20923. 숫자 할리갈리 게임

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

20923번: 숫자 할리갈리 게임

문제

인간이 가장 심심함을 느낀다는 오후 1시 22분, 도도와 수연이는 숫자 할리 갈리 게임을 하려 한다. 숫자 할리 갈리 게임의 규칙은 다음과 같다.

[숫자 할리 갈리 게임의 규칙]

1. 도도와 수연이는 각각 N장의 카드로 이루어진 덱을 배분받는다. 게임 시작 시 그라운드는 비어있는 상태이다.
   • 덱은 숫자가 보이지 않게 카드를 뒤집어 쌓아 놓은 카드 더미를 의미한다. 도도와 수연이는 자신의 덱을 가지고 게임을 진행하게 된다.
   • 그라운드는 카드를 내려놓게 되는 땅을 의미한다. 그라운드에 카드를 내려놓을 때는 자신의 그라운드에 카드를 내려놓으며, 그라운드에 카드 더미가 존재할 경우 카드 더미 위에 카드를 내려놓는 방식으로 게임을 진행한다.
2. 도도를 시작으로 도도와 수연이가 차례대로 자신이 가진 덱에서 가장 위에 위치한 카드를 그라운드에 숫자가 보이도록 내려놓는다.
3. 종을 치는 사람이 그라운드에 나와 있는 카드 더미를 모두 가져간다. 종을 치는 조건은 다음과 같다.
   • 그라운드에 나와 있는 각각의 카드 더미에서 가장 위에 위치한 카드의 숫자 합이 5가 되는 순간 수연이가 종을 친다. 단, 어느 쪽의 그라운드도 비어있으면 안된다.
   • 그라운드에 나와 있는 각각의 카드 더미 중 가장 위에 위치한 카드의 숫자가 5가 나오는 순간 도도가 종을 친다.
4. 종을 쳤다면, 상대방의 그라운드에 있는 카드 더미를 뒤집어 자신의 덱 아래로 그대로 합친 후 자신의 그라운드에 있는 카드 더미 역시 뒤집어 자신의 덱 아래로 그대로 가져와 합친다.
   • 종을 쳐서 그라운드에 있는 카드 더미를 가져가는 행위는 게임의 진행 순서에 영향을 미치지 않는다.

1. 한 명이 2-4번까지의 과정을 진행하는 것을 1번 진행한 것으로 보며 다음과 같은 방법으로 게임의 승패가 결정된다.
   1. 게임 진행 도중 자신의 덱에 있는 카드의 수가 0개가 되면 상대방이 승리한 것으로 본다.
   2.  M번 진행한 후 자신의 덱에 더 많은 카드를 지닌 사람이 승리한다.
   3.  M번 진행 후 각자의 덱에 있는 카드의 개수가 같다면 비긴 것으로 본다.

게임을 M번 진행한 후 승리한 사람은 누구일까?

입력

첫째 줄에는 도도와 수연이가 가지는 카드의 개수 N(1≤N≤30000)과 게임 진행 횟수 M(1≤M≤2500000)이 주어진다.

둘째 줄부터 N개의 줄에는 띄어쓰기로 구분하여 도도와 수연이가 가진 덱의 맨 아래에 위치한 카드에 적혀 있는 수부터 맨 위에 위치한 카드에 적힌 수까지 차례대로 주어진다. (각각의 카드는 1 이상 5 이하의 자연수가 적혀있다.)

출력

게임을 이긴 사람이 도도라면 do를 출력하고 게임을 이긴 사람이 수연이라면 su를 출력한다. 비겼을 경우, dosu를 출력한다.

풀이

Code(PyPy)