1158_요세푸스문제

www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

요세푸스 문제이다. n명 중 k번째 있는 사람을 탈락시키면서 탈락 된 순서대로 큐에 넣는 형태이다. 

생각보다 꼬여서 다시 한 번 생각했다. 

1) n이랑 k가 같을 때

2) n이 k보다 작을 때

를 고려해야 한다. 

#include<iostream>
#include<vector>
 
using namespace std;
 
vector<int> yp;
int cnt[5001];
vector<int> ans;
 
int main(void){
    int n, k, len, t;
 
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        yp.push_back(i);
    t = -1;
    for(int i = 0; i < n; i++){
        len = k;
        while(len){
            t++; t %= n;
            if(!cnt[t])
                len--;
        }
        ans.push_back(yp[t]);
        cnt[t] = 1;
    }
    cout << "<";
    for(int i = 0; i < n;i++){
        cout << ans[i];
        if(i == n - 1)
            break;
        cout << ", ";
    }
    cout << ">"<< "\n";
}