[백준] 1158 요세푸스 문제

문제 설명

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

1158번: 요세푸스 문제

1번부터 n번까지 n명의 사람이 원을 이루며 앉아있을 때, 순서대로 k번째 사람을 제거

원에서 사람들이 제거 되는 순서를 요세푸스 순열이라고 하는데, 이 순열을 구하기

 

문제 풀이법

queue를 쓰면 금방 풀린다

 

우선 1번부터 n번까지의 사람을 queue에 넣어놓고, queue가 empty가 되지 않을때까지 while문을 반복한다

while문에서는 k번째의 사람을 구하기 위해서, k -1 번째의 사람은 pop한 뒤, 다시 뒤에 push 한다

k번째 사람은 pop을 한 후, 출력하며, 다시 뒤에 push 하지 않는다

 

계속 반복하여 n명의 사람이 최종적으로 pop이 되면 종료한다 

 

소스 코드

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    
    queue<int> q;
    
    for (int i = 0; i < n; i++)
        q.push(i + 1);
    
    printf("<");
    while (!q.empty())
    {
        for (int i = 0; i < k - 1; i++)
        {
            q.push(q.front());
            q.pop();
        }
        printf("%d", q.front());
        q.pop();
        if (!q.empty())
        {
            printf(", ");
        }
    }
    printf(">");
    
    return 0;
}