[백준]1158번 요세푸스 문제

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

1158번: 요세푸스 문제

문제 정리: 요세푸스를 이해하고 입력값 N, K를 이용하여 요세푸스 순열을 출력한다.

 

이 문제를 통해 요세푸스를 알게되었는데 원리 자체는 간단하며, 그림을 그려보면 금방 이해할 수 있다.

주의할 것은 시작이 1이지만 한 개가 제거된 후에는 제거된 다음번째 숫자가 시작이 된다는 점이다.

(7,3)-요세푸스 순열-[시작N-제거N으로 따라가면 된다.]

문제 풀이:

시작점부터 순서대로 검사하는데 제거할 대상이면 제거하고 그 다음부터 검사,

                                                     제거할 대상이 아니면 맨뒤로 보내고 그 다음부터 검사

이 동작과정에서 큐(queue)를 떠올릴 수 있다.

 

이 문제는 출력 문제이기 때문에 N이라면 출력, 아니라면 queue.push로 맨 뒤로 보내는 방식을 사용하였다.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    queue <int> Josephus,Nqueue;
    int N,K,check=1;
    cin>>N>>K;

    for(int i=1;i<=N;i++)//1~N
        Nqueue.push(i);  
    cout<<"<";
    //Nqueue.size()가 0이 될 때까지
    while(Nqueue.size()!=1)//마지막숫자만 따로 출력하기 위해 1일때 while 탈출함
    {
        int newInput=Nqueue.front();
        if(check==K){ 
            cout<<Nqueue.front()<<", ";
            check=1;
        }else
        {
            Nqueue.push(Nqueue.front());
            check++;
        }
        Nqueue.pop();
    }
    cout<<Nqueue.front()<<">"; 
    return 0;
}

 

+)혹시 문제의 출력과 입력을 동일하게 했는데 '틀렸습니다' 오류가 뜬다면 반례도 잘 출력하는지 확인해보자.

입력: 5 5

출력: <5, 1, 3, 4, 2>