[BOJ S1][C++] 백준 20923번: 숫자 할리갈리 게임

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

20923번: 숫자 할리갈리 게임

 

문제

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

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

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

   

5.  M$M$번 진행한 후 자신의 덱에 더 많은 카드를 지닌 사람이 승리하고 M$M$번 진행 후 각자의 덱에 있는 카드의 개수가 같다면 비긴 것으로 본다. 게임 진행 도중 자신의 덱에 있는 카드의 수가 0$0$개가 되는 즉시 상대방이 승리한 것으로 본다. (둘 중 한 명이 2~4번까지의 과정을 진행하는 것을 1$1$번 진행한 것으로 본다.)

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

입력

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

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

출력

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

 

풀이

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

typedef deque<int> d;

d doCard, suCard;
d doGround, suGround;

// 종친사람의 카드덱에 상대의 그라운드 덱과 자신의 그라운드 덱을 합치는 합수
void mergeCard(d &winnerCard, d &loserGround, d &winnerGround) {
    for(int i=0; !loserGround.empty(); i++) {
        winnerCard.push_front(loserGround.front());
        loserGround.pop_front();
    }
    for(int i=0; !winnerGround.empty(); i++) {
        winnerCard.push_front(winnerGround.front());
        winnerGround.pop_front();
    }
}

// 그라운드에 카드를 내놓을때마다 종 칠 여부를 결정하여 종을 친다.
void hitBell() {
    // groundTop=0 : 그라운드가 비어있음
    int doGroundTop=0, suGroundTop=0;
    if(!doGround.empty())
        doGroundTop = doGround.back();
    if(!suGround.empty())
        suGroundTop = suGround.back();
    
    // 수연이가 종침 (그라운드가 비어있지 않아야하고, 합이 5여야함)
    if(doGroundTop!=0 && suGroundTop!=0 && doGroundTop+suGroundTop==5)
        mergeCard(suCard, doGround, suGround);
    
    // 도도가 종침 (둘중 하나가 5여야함)
    if(doGroundTop==5 || suGroundTop==5)
        mergeCard(doCard, suGround, doGround);
    
    // 종 안침
    return;
}

string solution(int n, int m) {
    // 할리갈리 수행
    bool doTurn = true;
    while(m--){
        if(doTurn) {
            // 인덱스가 작을수록 아래쪽에 위치한 카드 => back이 카드의 꼭대기쪽 방향이다
            doGround.push_back(doCard.back());
            doCard.pop_back();
            if(suCard.empty() || doCard.empty()) break; // 둘 중 한명이라도 갯수가 0이되면 게임 종료
            hitBell();
        } else {
            suGround.push_back(suCard.back());
            suCard.pop_back();
            if(suCard.empty() || doCard.empty()) break;
            hitBell();
        }
        
        doTurn = !doTurn;
    }

    // 승자 결정
    if(suCard.size() > doCard.size())
        return "su";
    else if (suCard.size() < doCard.size())
        return "do";
    else
        return "dosu";
}

int main() {
    int n,m;
    cin >> n >> m;
    doCard.assign (n,0);
    suCard.assign (n,0);
    for(int i=0; i<n; i++)
        cin >> doCard[i] >> suCard[i];

    cout << solution(n, m);
    
    return 0;
}

/*
 */