BOJ 1158번 요세푸스 문제

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

1158번: 요세푸스 문제

 

링크드리스트를 이용,

K는 몆번째를 의미하기 때문에 자신을 포함하려면 K-1 번만 카운트 해가는 식으로 문제를 해결해주면 된다.

 

#include <iostream>
#include <list>
#include <queue>
using namespace std;
 
queue<int> q;
list<int> l;
list<int>::iterator it, finish;
 
int main() {
    int N, K;
    cin >> N >> K;
    for (int i = 1; i <= N; i++) l.push_back(i);
    it = l.begin();
    /*
    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
    4
    */
 
    while (!l.empty()) {
        int cnt = 1;
        while (cnt < K) {
            if (it == --l.end()) it = l.begin();
            else it++;
            cnt++;
        }
        q.push(*it);
        if (it == --l.end()) {
            it = l.erase(it);
            it = l.begin();
        }
        else it = l.erase(it);
    }
 
    cout << "<" << q.front();
    q.pop();
    while (!q.empty()) {
        cout << ", " << q.front();
        q.pop();
    }
    cout << '>';
    return 0;
}