요세푸스 문제

요세푸스 문제란

마지막 한명이 남을 때까지 규칙에 따라 자신들을 죽이는 문제다. 로마군이 패배 직전에 집단자살을 감행했을 때 살아남고 싶었던 요세푸스의 이름을 본따 만든 문제다.

주어진 사람의 수에서 정해진 사람의 수가 뒤로 줄을 가게되고 그 후에 남은 사람이 자살한다.

아이디어

앞에서 사람들이 빠져서 뒤로 사람들이 줄을 서기 때문에 원형큐의 구조와 동일하다. 따라서 큐를 활용하여 문제를 푼다.

구현

while (q.Size() != 1) {
    for (int i = 0; i < k - 1; i++) {
        int next = q.Front();
        q.Dequeue();
        q.Enqueue(next);
    }
    q.Print();
    cout << "Executed: " << q.Front() << endl;
    q.Dequeue();
    q.Print();
}
cout << "Survivor: " << q.Front() << endl;