[BOJ] 20923번_숫자 할리갈리 게임_구현 (C++)

[문제]

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

숫자 할리갈리 게임을 만드는 게임 룰은 아래와 같다.

1. 도도와 수연이는 각각 N장의 카드로 이루어진 덱을 받는다. 게임 시작 시 그라운드는 비어있다.

• 그라운드는 카드를 내려놓게 되는 땅을 의미한다. 그라운드에 카드를 내려놓을 땐 자신의 그라운드에 카드를 내려놓으며, 그라운드에 카드가 존재할 경우 그 카드 위에 카드를 내려놓는 방식으로 진행한다.

2. 도도부터 시작해서 돌아가며, 자신의 덱 맨 위에서 숫자가 보이도록 그라운드에 카드를 내려놓는다.

3. 종을 치는 사람이 그라운드에 나와 있는 카드 더미를 모두 가져간다.

• 그라운드에 나와 있는 수의 합이 5가 되면 수연이가 종을 친다. (어느 쪽의 그라운드도 비어있으면 안됨)
• 그라운드에 나와 있는 수가 5인 경우 도도가 종을 친다.

4. 종을 쳤으면, 상대방의 그라운드에 있는 카드 더미를 뒤집어 자신의 덱 아래로 그대로 합친 후 자신의 그라운드에 있는 카드 더미도 뒤집어 자신의 덱 아래로 가져와 합친다.

• 종을 쳐서 그라운드에 있는 카드를 가져가는 행위는 게임 진행 순서에 영향을 미치지 않는다.

5. 한명이 2~4번까지의 과정을 진행하는 것을 1턴으로 보며, 다음과 같은 방법으로 게임의 승패가 결정 된다.

• 게임 진행 도중 자신의 덱에 있는 카드의 수가 0개가 되면 상대방이 승리한다.
• M번 진행한 후 자신의 덱에 더 많은 카드를 지닌 사람이 승리한다.
• M번 진행 후 각자의 덱에 있는 카드의 개수가 같다면 비긴 것으로 본다.

게임을 M턴 진행한 후 승리한 사람이 누구인지 출력하는 문제이다.

[사용 알고리즘]

deque(덱)

[풀이 핵심]

• 카드를 위, 아래에서 넣고 빼는 과정이 존재하므로 deque를 사용해서 구현하는 것이 좋다.
• 구현 문제이므로, 문제에 주어진 내용을 하나씩 구현하는 것이 좋다.

  1. 도도와 수연이의 덱과 그라운드를 deque로 만들고, N만큼 카드를 입력받아 각각의 덱에 push 한다. (덱 맨 아래의 카드부터 맨 위에 위치한 카드 순으로 입력되므로 push_front를 이용한다.)
  2. 매 턴 turn이라는 변수를 true와 false로 스위칭해가며 누구의 턴인지 확인하는 것이 중요하다.
     만약 도도의 턴이라면 아래와 같이 카드를 그라운드에 카드를 내려놓는다.
     dodo_ground.push_front(dodo.front());
     dodo.pop_front();
  3. if문을 통해 도도와 수연이중 누가 종을 칠 수 있는 지 확인한다.
  4. 종을 친 사람은 상대의 그라운드에 있는 카드를 아래에서부터 하나씩 자신의 덱 맨 아래에 넣고, 자신의 그라운드에 있는 카드도 아래에서부터 하나씩 자신의 덱 맨 아래에 넣는다.
  5. while문을 통해 count를 늘려가며 턴을 세어주며 도도와 수연이의 덱 size()를 확인해 승패를 결정해준다.

[코드]

//boj20923번_숫자 할리갈리 게임_구현

#include<iostream>
#include<deque>

using namespace std;

int N, M;

deque<int> dodo;
deque<int> dodo_ground;

deque<int> suyeon;
deque<int> suyeon_ground;

bool turn = false;

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		int card_do, card_su;
		cin >> card_do >> card_su;

		dodo.push_front(card_do);
		suyeon.push_front(card_su);
	}

	int count = 0;

	while (count < M) {
		if (!turn) {
			dodo_ground.push_front(dodo.front());
			dodo.pop_front();
		}
		else {
			suyeon_ground.push_front(suyeon.front());
			suyeon.pop_front();
		}

		if (dodo.size() == 0) {
			suyeon.push_back(1);
			break;
		}
		else if (suyeon.size() == 0) {
			dodo.push_back(1);
			break;
		}

		if ((!dodo_ground.empty() && !suyeon_ground.empty()) && (dodo_ground.front() + suyeon_ground.front()) == 5) {
			while (!dodo_ground.empty()) {
				suyeon.push_back(dodo_ground.back());
				dodo_ground.pop_back();
			}
			while (!suyeon_ground.empty()) {
				suyeon.push_back(suyeon_ground.back());
				suyeon_ground.pop_back();
			}
		}
		else if ((!dodo_ground.empty() && dodo_ground.front() == 5) || (!suyeon_ground.empty() && suyeon_ground.front() == 5)) {
			while (!suyeon_ground.empty()) {
				dodo.push_back(suyeon_ground.back());
				suyeon_ground.pop_back();
			}
			while (!dodo_ground.empty()) {
				dodo.push_back(dodo_ground.back());
				dodo_ground.pop_back();
			}
		}

		turn = !turn;
		count++;
	}

	if (dodo.size() > suyeon.size()) {
		cout << "do";
	}
	else if (dodo.size() < suyeon.size()) {
		cout << "su";
	}
	else {
		cout << "dosu";
	}

	return 0;
}