백준 20923 (C++) 숫자 할리갈리 게임

최초 업로드: 2025-09-21 04:13:21

최근 수정 시간: 2025-09-21 04:13:21

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] 숫자 할리갈리 게임

[문제 링크](https://www.acmicpc.net/problem/20923)

## 문제 설명

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

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

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

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

## 입력

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

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

## 출력

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

## 풀이
지문에 나와있는 대로 구현하면 된다. 다만 카드를 가져가기 전에 내 덱이 비어있는 지를 확인해야 하고, 한 사람이 카드를 한번 내려놓는 것이 한 턴이라는 것을 유의해야 한다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int input[30'000][2];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;

deque<int> dodo, su;
 while(n--) {
 int a, b; cin >> a >> b;
 dodo.push_back(a);
 su.push_back(b);
 }

deque<int> dodo_ground, su_ground;
 for(int i=0;i<m;i++) {
 if(i%2==0) {
 dodo_ground.push_back(dodo.back());
 dodo.pop_back();
 if(dodo.empty()) {
 cout << "su";
 return 0;
 }

if(dodo_ground.back()==5) {
 while(!su_ground.empty()) {
 dodo.push_front(su_ground.front());
 su_ground.pop_front();
 }
 while(!dodo_ground.empty()) {
 dodo.push_front(dodo_ground.front());
 dodo_ground.pop_front();
 }
 }
 if(!su_ground.empty() && su_ground.back()+dodo_ground.back()==5) {
 while(!dodo_ground.empty()) {
 su.push_front(dodo_ground.front());
 dodo_ground.pop_front();
 }
 while(!su_ground.empty()) {
 su.push_front(su_ground.front());
 su_ground.pop_front();
 }
 }
 } else {
 su_ground.push_back(su.back());
 su.pop_back();
 if(su.empty()) {
 cout << "do";
 return 0;
 }

if(su_ground.back()==5) {
 while(!su_ground.empty()) {
 dodo.push_front(su_ground.front());
 su_ground.pop_front();
 }
 while(!dodo_ground.empty()) {
 dodo.push_front(dodo_ground.front());
 dodo_ground.pop_front();
 }
 }
 if(!dodo_ground.empty() && su_ground.back()+dodo_ground.back()==5) {
 while(!dodo_ground.empty()) {
 su.push_front(dodo_ground.front());
 dodo_ground.pop_front();
 }
 while(!su_ground.empty()) {
 su.push_front(su_ground.front());
 su_ground.pop_front();
 }
 }
 }
 }
 cout << (dodo.size()>su.size() ? "do" : dodo.size()<su.size() ? "su" : "dosu");
}
```