[백준] 11866번 : 요세푸스 문제 0

문제

 

---

풀이

 

TMI지만 고등학교 수학선생님께선 원순열을 가르치실 때 약간 과격한 비유를 사용하셨다.

뭐...총으로 쏜다거나...기절을 시킨다거나 아무튼 그 덕에 그 파트를 제대로 배우고 지금까지 기억하니 나쁘지 않았던 것 같다.

 

아무튼

원을 일자로 펴보고 제일 앞에 총을 든 괴한이 있다고 하자. 너무 잔인하니까 마취총이라고 하자.

이 괴한은 3(=K)번째 사람만 공격한다. 1~8(=N)명의 사람들은 두려움에 떨며 그 괴한 앞에 줄서있다.

 

괴한은 3번째 사람만 공격하니 1번 사람을 다시 줄 뒤로 보낼 것이다.(pop->push) 2번 사람도 다시 줄 뒤로 보내고, 3번 사람을 만났을 때 마취총을 쏠 것이다.(pop) 모든 사람이 마취총에 맞을 때까지(size=0) 진행하면 되겠다.

---

소스코드

 

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue <int> q;
    int N, K;

    cin >> N >> K;
    for (int i = 1; i <= N; i++)
        q.push(i);
    cout << "<";
    while (q.size() != 1) { //출력 때문에 1개 남으면 빠져나올 것
        for (int i = 0; i < K - 1; i++) { //뽑아야 할 수 나오기 직전까지 큐 옮겨줌
            int tmp = q.front();
            q.pop();
            q.push(tmp);
        }
        cout << q.front() << ", ";
        q.pop(); //빵야
    }
    cout << q.front() << ">"; //마지막 남은 수 출력
}