[백준 1168] 조세퍼스 문제 2

https://www.acmicpc.net/problem/1168

1~n 까지 배열을 만들고 인덱스를 업데이트 하면서 해당 인덱스 값을 빼오고 배열에서 제거한 후 다음 인덱스로 넘어갑니다.

인덱스 업데이트 과정

x번째 인덱스에서 값을 빼왔으면 다음 인덱스는 x+(m-1) 입니다. 그 이유는 x번째 인덱스를 제거한 후 이동하기 때문에 인덱스가 한칸 씩 당겨지고 +m-1만 이동해도 +m번째 인덱스에 접근하는 것과 같은 효과가 나옵니다.

그런데 x+(m-1)의 값이 전체 배열의 크기를 넘어갈 수 있으므로 (x+(m-1))%(현재 배열의 크기)로 나머지만 구하여 인덱스가 범위를 넘어갈 경우 다시 0번부터 접근 가능하게 해줍니다.

예를 들어 아래 표의 3번째 줄 인덱스는 4+(3-1) % 5 == 1 입니다.

이 과정을 배열의 원소가 없어질 때까지 합니다. (혹은 정답 배열의 크기가 n이 될 때까지)

index	answer	0	1	2	3	4	5	6
2	3	1	2	3	4	5	6	7
4	36	1	2	4	5	6	7
1	362	1	2	4	5	7
3	3627	1	4	5	7
2	36275	1	4	5
0	362751	1	4
0	3627514	4

C++ code

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    vector<int> arr(n);
    for(int i = 0; i < n ; i++){
        arr[i] = i+1;
    }
    int index = 0;
    vector<int> answer;
    while(!arr.empty()){
        index = (index + m -1 )%arr.size();
        answer.push_back(arr[index]);
        arr.erase(arr.begin()+index);
    }
    cout << "<";
    for(int i = 0; i < n; i++){
        cout << answer[i];
        if(i < n-1)
            cout << ", ";
    }
    cout << ">";
    return 0;
}