<백준 알고리즘> 1158번 조세퍼스 문제

조세퍼스 문제 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	10565	5229	4050	51.770%

문제

조세퍼스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ M ≤ N ≤ 5,000)

출력

예제와 같이 조세퍼스 순열을 출력한다.

예제 입력 1 

7 3

예제 출력 1 

<3, 6, 2, 7, 5, 1, 4>

  

   

<풀이과정>

큐를 이용해서 1부터 n까지 만들고 

원을 이루면서 돌아가는 것을  

큐에서 첫 번째를 뽑아서 다시 맨 뒤에 넣는 방식으로 설계 

항상 첫번 째를 가리키고 한 칸씩 움직이는 것을 m-1번씩 반복하면서 구현 

// n,m을 입력받는다. 
// 1~n까지 번호를 만들고 n다음에 다시 1이 오도록 한다. 
// m번째 번호를 순차적으로 제거하고 제거된 번호를 제거된 순서대로 저장한다. 
// 제거된 순서대로 번호를 출력한다. 
 
#include<iostream>
#include<queue>
using namespace std;
int main(){
    int n,m;
    queue<int> q;
    
    cin >> n >> m; // 숫자 입력 
    
    for(int i=1;i<=n;i++){
        q.push(i); // 1부터 n까지 차례대로 q에 넣는다. 
    }
    cout << "<";
    while(n--){ // n번 반복
        for (int i=1;i<m;i++) // m-1번 반복 
        {
            q.push(q.front());
            q.pop();
            // 1번 1,2,3,4,5,6,7 -> 2,3,4,5,6,7,1 
            // 2번 2,3,4,5,6,7,1 -> 3,4,5,6,7,1,2 
        }
        cout << q.front(); // 3을 출력
        q.pop(); // 4,5,6,7,1,2
        if(n!=0){
            cout <<", ";
        }    
    }
    cout << ">";
    return 0;
}

정답~!