Boj 11866 c++ 요세푸스 문제 0

요세푸스 문제.

 

숫자 n, m이 주어질 때

(n,m)-요세푸스 순열을 출력하는 알고리즘이다.

*요세푸스 순열이란?, (m<=n)의 수가 주어졌을 때 

원형을 이루고 있는 n개의 숫자 중에서 계속해서 m번째 숫자를 제거하는 순열로, 총 n개 만큼의 수를 나열하는 것이다.

 

이때, 제거되는 순서를 구하는 알고리즘을 구현하려면 큐를 사용해야 한다.

 

또한, push와 pop을 계속해서 반복함으로써 큐를 원형으로 생각할 수 있다. 

 

우선 n개의 연속한 숫자를 큐에 push 한다. 

그리고 m번째 숫자를 제거하기 위해 큐의 뒤에 front()값을 push하기 다시 pop하는 과정을 m-1번 반복한다.

그 이후 다시 한번 pop을 하면 m번째 사람만 제거되며, 숫자들은 여전히 원형을 이루게 된다.

이 과정을 큐가 빌 때까지 계속해주면 제거되는 숫자의 순서를 구할 수 있다

.

*숫자가 m개 이하로 남았을 때 m번째 사람을 어떻게 제거하는지 이해가 가지 않을 수 있다. 하지만, 반복문 내에서 push와 pop을 

계속해서 수행하기 때문에, 숫자의 개수가 줄어들지 않으면서 m번째 사람을 구할 수 있다

 

이때, m번째 숫자를 제거하기 전에 그 값을  저장해놓고 그 값을 다시 그대로 출력하면 요세푸스 순열이 된다.

하지만 n의 입력값이 1인 경우에는 예외처리를 해주어야 하는데, 이때는 항상 출력값이 <1>이 되기 때문이다. 

이를 구현한 코드는 다음과 같다.

 

 

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

int main(){
    int n, m;
    queue<int> q, ans;
    cin>>n>>m;
    for(int i=1; i<=n; i++){
     q.push(i);
     
      
     
}
      if(n==1){
        printf("<%d>", n);
          return 0;
}
    
    else{
    while(q.empty()!=1){
     for(int i=0; i<m-1; i++){
      q.push(q.front());
      q.pop();
      
}       ans.push(q.front());
        q.pop();
      
}   
    cout<<'<';
    while(ans.size()>1){
    cout<<ans.front()<<", ";
     ans.pop();

}
    cout<<ans.front()<<'>';
    }
    
}