요세푸스 문제란
마지막 한명이 남을 때까지 규칙에 따라 자신들을 죽이는 문제다. 로마군이 패배 직전에 집단자살을 감행했을 때 살아남고 싶었던 요세푸스의 이름을 본따 만든 문제다.
주어진 사람의 수에서 정해진 사람의 수가 뒤로 줄을 가게되고 그 후에 남은 사람이 자살한다.
아이디어
앞에서 사람들이 빠져서 뒤로 사람들이 줄을 서기 때문에 원형큐의 구조와 동일하다. 따라서 큐를 활용하여 문제를 푼다.
구현
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;