백준 20301번: 반전 요세푸스 (C++)

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

20301번: 반전 요세푸스

---

Solved By: Deque

 

뺀 사람의 수가 M명이 되었을 경우, 방향을 바꿔야 하기 때문에 큐가 아닌 덱을 사용하여 양방향을 고려하게 해주고,

M명이 되었을 때 bool type flag변수를 사용하여 방향을 바꿀지 말지에 대한 여부를 설정해줬습니다.

#include <iostream>
#include <deque>
using namespace std;

int main(){
    ios_base::sync_with_stdii(false);
    cin.tie(NULL);
    
    int n, k, m; cin >> n >> k >> m;
    deque<int> dq;
    for(int i = 1; i <= n; i++){
        dq.push_back(i);
    }
    
    int mcnt = 0;
    bool flag = 0;
    while(!dq.empty()){ // 모든 수 사용 == 덱 안에 있는 모든 수 사용
        int kcnt = 0; // k번쨰 사람
        if(mcnt == m){
            flag = (flag == 0) ? 1 : 0;
            mcnt = 0;
        }
        
        if(!flag){ // right direction
            while(true){
                int tmp = dq.front();
                dq.pop_front();
                dq.push_back(tmp);
                ++kcnt; // 덱으로 돌리면서 몇 번째인지 cnt
                if(kcnt == k){// k번째 사람을 찾은 경우
                    dq.pop_back();
                    ++mcnt;// 1명 뺐으니 mcnt++
                    cout << tmp << '\n';
                    break;
                }
            }
        }
        else{ // left direction
            while(true){
                int tmp = dq.back();
                dq.pop_back();
                dq.push_front(tmp);
                ++kcnt;
                if(kcnt == k){
                    dq.pop_front();
                    ++mcnt;
                    cout << tmp << '\n';
                    break;
                }
            }
        }
    }
}