1168번: 요세푸스 문제2

혼자 힘으로 풀지 못했다.

퍼포먼스를 만족키지 못했는데

다른 사람들의 풀이를 참조해서 vector의 erase를 사용하면 된다는 걸 알았다.

(erase는 memmove로 구현해서 매우, 매우 빠르다고 한다)

하지만 이 문제는 세그먼트 트리를 사용하라는 목적으로 만든 것 같다.

세그먼트 트리를 알아보자...

#include <iostream>
#include <vector>
 
int main(void) {
    int len, term;
    std::cin >> len >> term;
 
    std::vector<int> arr(len);
    for (int i = 0; i < len; i++) {
        arr[i] = i + 1;
    }
 
    int pos = -1;
    std::cout << "<";
    while (true) {
        pos = (pos + term) % arr.size();
        std::cout << arr[pos];
        if (arr.size() == 1) {
            std::cout << ">";
            break;
        }
        std::cout << ", ";
        arr.erase(arr.begin() + pos--);
    }
 
    return 0;
}