[BOJ][C++] 백준 20301번: 반전 요세푸스

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

20301번: 반전 요세푸스

 

문제

요세푸스 문제는 다음과 같다.

 1$1$번 사람 오른쪽에는 2$2$번 사람이 앉아 있고, 2$2$번 사람 오른쪽에는 3$3$번 사람이 앉아 있고, 계속하여 같은 방식으로 N$N$명의 사람들이 원을 이루며 앉아 있다. N$N$번 사람 오른쪽에는 1$1$번 사람이 앉아 있다. 이제 K$K$(≤N$\leq N$)번 사람을 우선 제거하고, 이후 직전 제거된 사람의 오른쪽의 K$K$번째 사람을 계속 제거해 나간다. 모든 사람이 제거되었을 때, 제거된 사람의 순서는 어떻게 될까?

이 문제의 답을 (N$\boldsymbol{N}$, K$\boldsymbol{K}$)–요세푸스 순열이라고 하며, (7$7$, 3$3$)–요세푸스 순열은 ⟨3,6,2,7,5,1,4⟩$\left<3, 6, 2, 7, 5, 1, 4\right>$가 된다.

하지만 한 방향으로만 계속 돌아가는 건 너무 지루하다. 따라서 요세푸스 문제에 재미를 더하기 위해 M$M$명의 사람이 제거될 때마다 원을 돌리는 방향을 계속해서 바꾸려고 한다. 이렇게 정의된 새로운 문제의 답을 (N$\boldsymbol{N}$, K$\boldsymbol{K}$, M$\boldsymbol{M}$)–반전 요세푸스 순열이라고 하며, (7$7$, 3$3$, 4$4$)–반전 요세푸스 순열은 ⟨3,6,2,7,1,5,4⟩$\left<3, 6, 2, 7, \mathbf{1}, \mathbf{5}, \mathbf{4}\right>$가 된다.

 N$N$, K$K$, M$M$이 주어질 때, (N$N$, K$K$, M$M$)–반전 요세푸스 순열을 계산해 보자.

입력

첫째 줄에 정수 N$N$, K$K$, M$M$이 주어진다. (1≤N≤5 000$1 \leq N \leq 5\ 000$, 1≤K,M≤N$1 \leq K, M \leq N$)

출력

(N$N$, K$K$, M$M$)–반전 요세푸스 순열을 이루는 수들을 한 줄에 하나씩 순서대로 출력한다.

 

풀이

[🏕️ ICPC Sinchon Novice] - [C/C++] 백준 1158번 : 요세푸스 문제

[C/C++] 백준 1158번 : 요세푸스 문제

 

반대방향도 구현해주면 된디

요세푸스 문제는 큐를 이용했다. 양방향을 위해 덱을 이용하자

 

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main() {
    int n, k, m;
    cin >> n >> k >> m;
    
    vector<int> ans;
    deque<int> q;
    for(int i=1; i<=n; i++)
        q.push_back(i);
    
    int turn = 1;
    bool isReverse = false;
    while(!q.empty()) {
        if(isReverse) {
            if(turn%k == 0) {
                ans.push_back(q.back());
                if(ans.size()%m == 0)
                    isReverse = !isReverse;
            }
            else q.push_front(q.back());
            q.pop_back();
        } else {
            if(turn%k == 0) {
                ans.push_back(q.front());
                if(ans.size()%m == 0)
                    isReverse = !isReverse;
            }
            else q.push_back(q.front());
            q.pop_front();
        }
        
        turn++;
    }
    
    for(int i: ans)
        cout << i << "\n";
        
    return 0;
}