[Silver 4] 2164번 카드2

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

2164번: 카드2

 

이 문제는 STL의 queue를 사용하여 해결하였다.

문제에서 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 

라는 힌트가 있었고, 입력 값인 N = 4인 경우 자료구조에 위에서부터 1, 2, 3, 4 순으로 들어와야한다. 

1을 버리고 2를 자료구조의 가장 뒤에 넣기 위해서 queue를 사용하였다.

 

반복은 queue의 크기가 1이 될때까지 하였으며 버리는 것과 옮기는 작업은 bool 변수인 trash를 사용하였다.

trash가 true인 경우 버리고 false인 경우 밑으로 옮기는 연산을 진행하였다.

 

마지막으로 반복을 빠져 나오면 queue의 크기가 1이므로 queue의 가장 앞에있는 요소를 출력하면 정답이 된다.

 

#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);
    
    bool trash = true;
    while(q.size() != 1){
        if(trash){
            q.pop();
            trash = false;
        }else{
            int card = q.front();
            q.pop();
            q.push(card);
            trash = true;
        }
    }
    cout<<q.front()<<'\n';
}