[백준] 2164 카드2

문제 설명

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

2164번: 카드2

1부터 N까지의 수가 있는 카드가 순서대로 놓여져 있고, 주어진 동작을 했을 때 제일 마지막에 남게되는 카드 구하기

• 가장 위에 있는 카드를 버림
• 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮김

=> 위 동작을 카드가 한 장 남을 때 까지 반복

 

문제 풀이법

1부터 N까지 순서대로 카드가 놓여있기에 queue를 사용한다

 

우선 1부터 N까지 queue에 값을 넣어준 후, 카드의 개수가 1보다 클 동안 while문을 반복한다

while문 내에서는 제일 위에 있는 카드를 pop한 후, 카드의 개수가 1인지 확인하는 과정을 거친다

만일 개수가 1이 아니라면, 맨 위의 카드를 뒤에 push 한 후, 앞의 카드를 pop한다 

 

소스 코드

#include <iostream>
#include <queue>

using namespace std;


int main()
{
    int n;
    cin >> n;
    
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        q.push(i);
    }
    
    while (q.size() != 1)
    {
        q.pop();
        if (q.size() == 1)
            break;
        q.push(q.front());
        q.pop();
    }
    
    printf("%d\n", q.front());
    return 0;
}