[1158번] 요세푸스 문제

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

1158번: 요세푸스 문제

 

1부터 n명까지의 사람이 원형으로 있다고 생각해보면,

k번째 사람을 제거하는 것인데 제거하고 난 후에도 사람이 0명이 될 때까지 계속 k번째 사람을 제거하고, 제거되는 차례대로 출력하는 문제입니다.

 

큐의 성질을 이용하여 요세푸스 문제를 풀어보았습니다.

k번째 사람을 제거해야 하므로 k-1번째까지의 사람은 빼서 다시 큐에 넣어주고, k번째 사람을 출력한 후 큐에서 제거합니다.

이를 큐가 비게 될 때까지 반복해주면 됩니다.

또한 문제의 출력 형식에 맞추기 위해 큐에 데이터가 있는 경우에만 콤마를 출력해주면 됩니다.

 

 

[코드]

#include <iostream>
#include <queue>
using namespace std;
int main () {
    int n, k; // 1부터 n명의 사람을 순서대로 k번째 사람을 제거
    cin >> n >> k; 
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }
    cout << '<';
    while (!q.empty()) {
        for (int i = 0; i < k - 1; i++) {
            int tmp = q.front();
            q.pop();
            q.push(tmp);
        }
        cout << q.front();
        q.pop();
        if (!q.empty()) cout << ", ";
    }
    cout << '>' << '\n';
    return 0;
}

 

[결과]

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