11866: 요세푸스 문제 0 - queue

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

 

문제요약

원소 개수 n, 제거해야하는 사람 k 요세푸스 순열을 출력하라!

 

난이도

Silver 5

---

풀이 포인트

• 그리디
  • 가장 첫번째 회의는 진행한다고 가정하고 그 다음에 열 수 있는 회의부터 고려

---

REVIEW

 

진짜 바보처럼 k를 3일 때만 가정하여 풀이를 구현했다가 틀렸다. 

queue를 활용하여 연속하는 순열만들기!

쉽게 풀리니 문제 풀이가 재밌다 ㅎ

 

 

---

CODE

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

int n, k;
queue<int> q;
vector<int> v;

int main(){
    cin >> n >> k;

 
    for(int i = 1; i <= n; i++){
        q.push(i);
    }

    while(!q.empty()){

        for(int i = 0; i < k-1; i++){
            int first = q.front();
            q.pop();
            q.push(first);
        }
        
        int toRemove = q.front();
        q.pop();
        v.push_back(toRemove);
    }


    cout << "<";
    for(int i = 0; i < v.size(); i++){
        if (i != 0) cout << ", ";
        cout << v[i];
    }
    cout << ">";

}