BOJ 백준 1158 : 조세퍼스 순열

(N-K) 조세퍼스 순열이란 숫자 N과 K가 주어질때, N은 1~N까지의 숫자가 원형테이블에 앉아있는것으로, K는 그 N명을 K번째마다 삭제해 나가는간다.

예를 들어 N이 7일때, 1~7번까지의 사람이 원형으로 앉아있다. K가 3일때, 1 2 3 4 5 6 7 / 1 2 4 5 6 7 / 1 2 4 5 7 / 1 4 5 7/  1 4 5/ 1 4 / 1순으로 삭제된다.

Queue를 이용하여 풀수 있다.

#include <queue>

queue<int> q;

q.push(N);
q.pop();
q.empty();
q.front();
q.back();
q.size();

Queue는 위와같이 사용할 수 있다.

이때, front()와 back()은 메모리 위치값을 알려주는것이 아니라, 들어있는 내용물의 값을 알려준다. 

N번째의 값이 아니면, pop()한값을 다시 queue에 push() 해준다. N 번째 값일때는 push하지않는다. 큐에 데이터가 남아있지 않을때까지 이작업을 반복한다.

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N,K;
    int count=1;
    
    cin>>N>>K;
    
    queue<int> q;
    
    for(int i=1; i<=N; i++)
        q.push(i);
    
    cout<<"<";
    while(!q.empty())
    {
        if(count!=K){
            
            q.push(q.front());
            q.pop();
            count++;
        }else if(count==K){
            if(q.size()!=1){
                cout<<q.front()<<", ";
            }else if(q.size()==1){
                cout<<q.front();
            }
            q.pop();
            count=1;
        }
    }
    cout<<">";
    
    return 0;
}

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

1158번: 조세퍼스 문제