[BOJ] 2164 카드2

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

2164번: 카드2

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

queue

 

---------------------------------------------------풀이----------------------------------------------------

 

카드의 제일 위를 queue의 front라고 생각하자.

제일 위의 카드를 버리는 행위는 pop과 일치하고,

제일 위의 카드를 맨 아래로 옮기는 행위는 pop과 push를 동시에 하는 것과 일치한다.

 

먼저, 1부터 N까지 큐에 넣는다.

그 다음부터는 카드가 한 장 남을 때까지

mode가 0이면 제일 위의 카드를 버리고, 1이면 카드를 맨 아래로 옮기는 과정을 번갈아가며 반복한다.

mode를 xor 1 시킴으로써 0과 1이 번갈아 나타나도록 하였다.

마지막에 카드가 한 장 남을 경우, queue의 front를 출력한다.

 

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

// (위)1-2-...-N(아래)
// 제일 위에 있는 카드 버림->제일 위에 있는 카드를 맨 아래로 옮김. 
// 카드가 한 장 남을 때까지 반복
int main(void){
    FASTIO;
    int N;
    cin >> N;
    queue<int> q;
    for(int i = 1; i <= N; i++){
        q.push(i);
    }
    int mode = 0;
    while(q.size() > 1){
        if(mode == 0){
            q.pop();
        }
        else{
            q.push(q.front());
            q.pop();
        }
        mode ^= 1;
    }
    cout << q.front() << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

매우 간단한 queue 전용 문제.