백준 1158 - 요세푸스 문제(C++)

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

1158번: 요세푸스 문제

 

풀이

1~n까지의 수가 담긴 큐에서 k번째의 수를 반복적으로 제거하면 된다. 하지만 중간에 있는 값을 제거하는 것은 쉽지 않으니 큐를 사용한다.

 

1) k-1번을 반복하며 앞의 수를 빼서 맨 뒤에 넣는다.

2) 그 후에 k번째의 수를 제거한다.

이 과정을 큐에 남은 수가 없을 때까지 반복한다.

 

코드

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue<int> q;
    int a,b;
    cin>>a>>b;
    for(int i=1; i<=a; i++)
    {
        q.push(i);
    }

    int tmp;
    cout<<'<';
    while(q.size()>1)
    {
        for(int i=1; i<b; i++)
        {
            tmp = q.front();
            q.push(tmp);
            q.pop();
        }
        cout<<q.front()<<", ";
        q.pop();
    }
    cout<<q.front()<<'>'<<'\n';
}