백준 11866 C++

#include <iostream>
#include <queue>

using namespace std;

int n, k, tmp;

queue<int> q;

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> k;
    
    for(int i = 1; i <= n; i++){
        q.push(i);
    }
    
    cout << '<';
    
    while(q.size() > 1){
        for(int i=0;i<k-1;i++){
            tmp = q.front();
            q.push(tmp);
            q.pop();
        }
        
        tmp = q.front();
        cout << tmp << ", ";
        q.pop();
    }
    
    tmp = q.front();
    
    cout << tmp << ">\n";
    
	return 0;
}

처음에 주어진 숫자가 7 3이라면
원을 이루고 있는 사람은 1 2 3 4 5 6 7 형태이다.


1회차에는 3번이 제거된다.

1 2 X 4 5 6 7

2회차에는 4부터 시작해서 3번째인 6번이 제거된다.

1 2 X 4 5 X 7

3회차에는 7부터 시작해서 3번째인 2번이 제거된다.

1 X X 4 5 X 7

4회차에는 4부터 시작해서 3번째인 7번이 제거된다.

1 X X 4 5 X X

5회차에는 1부터 시작해서 3번째인 5번이 제거된다.

1 X X 4 X X X

6회차에는 1->4->1이므로, 1번이 제거된다.

X X X 4 X X X

7회차에는 남은 마지막 숫자인 4번이 제거된다.

따라서 이때 결과로 얻어진 요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N개의 수가 있을 때 N회차까지 실행하는데, 마지막에는 하나만 남아있으므로 while문은 N-1회차까지 실행하면 된다. queue에 2개가 남아있을 때까지만 실행한다.

반복문 내에서는 현재 queue의 가장 앞에 있는 수를 queue의 뒤에 추가하고, 추가한 수는 제거하는 방식으로 K번째 수를 찾는다.