Baekjoon 문제 11866번 요세푸스 문제 0

문제 출처:https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

Baekjoon 11866번 문제 요세푸스 문제 0

---

문제 분석

출처 : https://www.gleammath.com/post/solve-this-deadly-puzzle-investigating-the-josephus-problem

해당 문제는 요세푸스 순열이라하는 문제입니다. 없어지는 자리를 순서대로 출력하면 되죠. 이 문제는 queue로 해결할 수 있습니다. 자리에서 일어나서 다시 맨 뒤로 앉는다고 생각하면 이해가 쉬울 것입니다. 

1. 1번부터 N번까지 queue에 넣습니다.                        O(n)
2. count = K - 1로 설정합니다 (자신의 순번 제외)
3. queue가 empty가 될 때까지 loop를 돌립니다:            O(n)
   1. 의자에서 한 사람이 일어납니다. (num) - pop
   2. count가 0인 경우, K번째 사람이므로 빼주고 count를 K - 1으로 초기화해줍니다.
   3. 0이 아닌 경우, count를 1 감소시키고 의자에서 일어났던 사람이 다시 제일 끝에 앉습니다. - push

Total Time Complexity: O(n)

---

코드는 다음과 같습니다:

#include <iostream>
#include <queue>
using namespace std ;
int main(){
    ios::sync_with_stdio(false) ;
    cin.tie(NULL) ;     cout.tie(NULL) ;
    queue<int> q ;
    int N, K, cnt ;
    cin >> N >> K ;
    for(int i = 1 ; i <= N ; i++)
        q.push(i) ;
    cnt = K - 1;
    cout << "<" ;
    while(!q.empty()){
        int num = q.front() ;
        q.pop() ;
        if(0 == cnt){
            if(q.empty())
                cout << num << ">" ;
            else
                cout << num << ", " ;
            cnt = K - 1;
        }
        else{
            q.push(num) ;
            cnt -= 1 ;
        }
    }
    return 0 ;
}

해당 문제는 Github에서도 보실 수 있습니다:

https://github.com/gurcks8989/CodingTest/blob/master/BackJoon/HPS/P11866_Josephus_Problem_0.cpp

GitHub - gurcks8989/CodingTest: CodingTest_study_with_c++

훈수 및 조언은 언제든 환영입니다.