[백준/C,C++] 11866번: 요세푸스 문제 0

www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

STL인 vector로 쉽게 해결이 가능한 문제입니다. 현재 지울 번호는 (index + k - 1) % size로 나타낼 수 있는데, 예제의 입력대로 n이 7, k가 3인 경우로 생각해보겠습니다. 1 2 3 4 5 6 7의 수열 중 처음 지워지는 번호는 (0 + 2) % 7로 2번인 3이 됩니다. 다음은 1 2 4 5 6 7의 수열 중 지워지는 번호는 (2 + 2) % 6으로 4번인 6이 됩니다. 1 2 4 5 7의 수열 중 지워지는 번호는 (4 + 2) % 5로 1번인 2가 되죠.

#include<iostream>
#include<vector>

using namespace std;

int main(void)
{
    int n, k; cin >> n >> k;
    vector<int> v(n);

    for (int i = 0; i < n; i++) {
        v[i] = i + 1;
    }

    int size = v.size();
    int idx = 0;
    cout << "<";
    while (size > 0) {
        idx = (idx + k - 1) % size;
        if (size == 1) cout << v[idx] << ">";
        else cout << v[idx] << ", ";
        v.erase(v.begin() + idx);
        size = v.size();
    }

    return 0;
}

큐를 이용해서 앞의 숫자들을 뒤로 계속 push 해주며 front에 해당하는 번호를 pop 해주거나, 원형 연결 리스트를 통해 좀 더 직관적으로 구현할 수도 있지만, 나머지 연산을 통해 지울 번호를 계속 갱신해줄 수 있기 때문에 벡터로 간단히 해결해 보았습니다.