[Algospot] 알고스팟 JOSEPHUS 조세푸스 문제

출처: https://www.algospot.com/judge/problem/read/JOSEPHUS#

 Input 

2

6 3

40 3

 

 Output 

3 5

11 26

 

N = 6, K = 3 ▷ 숫자 = 1  2  3  4  5  6

① 1 제외: [2 3 4 5 6]

② 4 제외: [2 3 5 6]

③ 2 제외: [3 5 6]

④ 6 제외: [3 5]

 

[구현] -연결 리스트 이용.

리스트 크기가 넘을 때 처음부터 다시 count 하는 것만 주의하면 K 번째를 쉽게 count

---

#include <iostream>
#include <list>
using namespace std;
int C, N, K;
 
void josephus(){
    list<int> survivor;
    // 1 ~ N 숫자 push 
    for (int i = 1; i <= N; i++) survivor.push_back(i);
    
    list<int>::iterator kill = survivor.begin();
    while (N > 2) {
        kill = survivor.erase(kill);
        if (kill == survivor.end()) kill = survivor.begin();
        N--;
        // K번째 떨어진 숫자를 제외
        for (int i = 0; i < K - 1; i++) {
            kill++;
            // 리스트 탐색이 순화되도록
            if (kill == survivor.end()) kill = survivor.begin();
        }
    }
    cout << survivor.front() << " " << survivor.back() << endl;
}
 
int main(){
    cin >> C;
    while (C--) {
        cin >> N >> K;
        josephus();
    }
}