문제 출처

1. 문제설명

  • 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있다.
  • 양의 정수 K가 주어지는데, K번째 사람을 제거한다.
  • 제거된 순서(요세푸스 순열)를 구하라



2. 알고리즘 설계

  • 자료구조 queue를 이용해서 N까지 숫자를 push한다.
  • K번째가 아닐 때까지 큐에 push & pop 해주고,
  • 이후에 front 값을 정답 배열에 넣는다.



3. 로직

  • 큐의 size가 K보다 적을 수 있기 때문에
  • 나머지 연산(%)을 사용하였다.



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

bool visited[5001] = { false, };

int main(void) 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    queue<int> q;
    int N, div; cin >> N >> div;
    for (int i = 1; i <= N; i++)
        q.push(i);

    int idx = 1;
    vector<int> ans;
    while (!q.empty()) {
        while (idx % div != 0) {
            q.push(q.front());
            q.pop();
            idx++;
        }
        idx = 1;
        ans.push_back(q.front());
        q.pop();
    }

    cout << '<';
    for (int i = 0; i < ans.size() - 1; i++)
        cout << ans[i] << ", ";
    cout << ans[ans.size() - 1] << '>';
    return 0;
}