2021-06-03 · 2분

백준 1158번 요세푸스

algorithmboj

이 글은 작성된 지 2년이 넘었어요. 내용이 오래됐을 수 있어요.

백준 1158번 문제 : https://www.acmicpc.net/problem/1158

[알고리즘] - 큐(queue) 에서 배운 큐를 활용하여 문제를 해결할 것입니다!

문제 해결

전산학이나 수학에서 요세푸스 문제(Josephus problem) 혹은 요세푸스 순열(Josephus permutation)은 다음과 같이 정의한다.

_n_과 _k_가 자연수이고, k < _n_이라고 가정한다. _n_명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 나가서 _k_번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 _k_번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.

풀이 과정

c++ STL에서 지원해주는 queue을 사용하였다.

(7, 3)이라고 했을때

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

N - 1번까지 push후 pop해 주고

N 일때 front후 pop을 반복 해주면 해결 될 것 같습니다.

코드

#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;
}