[BOJ/백준] 2164번 카드2 (c++)

문제 

• 문제
  • N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
  • 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
  • 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
  • N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

• 입력
  • 첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

• 출력
  • 첫째 줄에 남게 되는 카드의 번호를 출력한다.

 

 

문제 링크 

2164번: 카드2

 

문제 풀이 

 

이 문제는 큐(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";
}