N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
이 문제는 큐(queue) 문제입니다. 큐는 선입선출(FIFO, First-In-First-Out) 구조를 가지는 자료구조로, 주어진 문제에서는 카드를 관리하는 데에 활용하고 있습니다. 각각의 카드는 번호가 붙어 있으며, 제일 위(앞)에 있는 카드가 가장 먼저 제거되고, 그 다음 제일 위에 있는 카드가 밑으로 옮겨지는 과정을 반복하게 됩니다.
큐(Queue) 자료구조란?
큐는 자료를 저장하는 구조로, 새로운 데이터가 들어오면 뒤(Back)에 추가되고,
제거할 때는 앞(Front)에서 제거됩니다.
이러한 특성 때문에 큐는 후입선출(LIFO, Last-In-First-Out) 구조인 스택과는 달리
선입선출(FIFO) 구조를 가지게 됩니다.
문제에서는 큐를 활용하여 카드를 관리하고, 맨 위에 있는 카드를 버리고 그 다음 맨 위에 있는 카드를 맨 아래로 옮기는 과정을 반복하게 됩니다. 이를 마지막 카드가 남을 때까지 수행하면 됩니다.
문제 코드
#include <iostream>
#include <queue>
using namespace std;
int main()
{
int n;
queue<int> card;
cin >> n;
for (int i = 1; i <= n; i++)
{
card.push(i);
}
while (card.size() > 1)
{
card.pop();
card.push(card.front());
card.pop();
}
cout << card.front() << "\n";
}