BOJ 1158 — Josephus Problem

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

---

We'll solve the problem using the queue learned in [Algorithm] - Queue!

Problem solving

In computer science and mathematics, the Josephus problem (or Josephus permutation) is defined as follows.

Assume n and k are natural numbers and k < n. When n people are gathered in a circle, you count the order starting from an arbitrary person and remove the k-th person from the group. From the remaining n-1 people, you again count the order from the next person and remove the k-th person. You keep repeating this until no one is left. The order in which people are removed from the group is called the (n, k) Josephus permutation, and the problem of finding the last person removed is called the Josephus problem.

Solution process

I used the queue supported by the C++ STL.

For (7, 3):

1. (1, 2, 3, 4, 5, 6, 7) ( )
2. (1, 2, 4, 5, 6, 7) ( 3 )
3. (1, 2, 4, 5, 7) ( 3 , 6 )
4. (1, 4, 5, 7) ( 3 , 6, 2 )
5. (1, 4, 5 ) ( 3, 6, 2, 7 )
6. (1, 4 ) ( 3, 6, 2, 7, 5 )
7. ( 4 ) ( 3, 6, 2, 7, 5, 1 )
8. ( ) ( 3, 6, 2, 7, 5, 1, 4 )

Push then pop up to N-1 times,

and for the Nth, repeating front then pop should solve it.

Code

See more

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

int main() {
    int N, K;
    queue<int> Queue;

    scanf("%d%d", &N, &K);
    fgetc(stdin);

    for (int i = 1; i <= N; i++)
    {
        Queue.push(i);
    }
    printf("<");
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = 0; j < K - 1; j++)
        {
            Queue.push(Queue.front());
            Queue.pop();
        }

        printf("%d", Queue.front()); printf(", ");
        Queue.pop();
    }
    printf("%d", Queue.front());
    printf(">\n");
    return 0;
}

---

Original (Korean): tistory — published 2021-06-03, migrated to this blog. This translation was generated with the help of AI.