cpp) 백준 11866: 요세푸스 문제 0

Problem

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

11866번: 요세푸스 문제 0

1번부터 N번까지 N명의 사람들이 원을 이루며 앉아있다. 양의 정수 K가 주어질 때, 순서대로 K번째 사람을 제거한다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 나타낸 (N,K) 요세푸스 순열을 구하시오.
 
 

Solution

#include<iostream>
#include<queue>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

    int n, k;
    cin >> n >> k;

    queue<int> q;

    // 초기화
    for(int i=1;i<=n;i++){
        q.push(i);
    }

    cout << '<';

    while(q.size()>1){
        // k-1까지는 push함으로써 뒤에 연결시킴 (원형큐 생성)
        for(int i=0;i<k-1;i++){
            q.push(q.front());
            q.pop();
        }
        // k번째는 수는 원형큐에서 완전히 없애줌
        cout << q.front() << ", ";
        q.pop(); 
    }

    cout << q.front() << '>';
    
    return 0;
}

 
- 이 문제는 선입선출 구조의 큐(Queue)를 이용하여 풀 수 있다.
- k번째인 경우만 제거하므로, 한 사이클의 1번째부터 k-1까지는 pop() 함수로 빼서 뒤에 다시 넣어준다.