BOJ 11866 요세푸스 문제 0

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

11866번: 요세푸스 문제 0

 

 

0. 문제 개요

N과 K값이 주어진다. N은 사람의 수, K는 죽는 순서이다. N명의 사람이 둥글게 앉는다. K번째 사람이 한 명씩 죽는다. 이때 죽은 사람은 K번째 숫자를 셀 때 포함시키지 않는다.

 

 

 

 

1. 문제 해결 아이디어

종만북의 풀이를 참고했다.

Vector를 이용해서 풀 수도 있지만 Queue를 이용해보자.

먼저 일반적인 queue는 일직선 형태이기 때문에 이를 원형 큐처럼 이용할 수 있는 방법을 생각해야 한다.

 

다음 원형 큐를 탐색하는 순서는 다음과 같다. 1 - 2 - 3 - 4 - 1 - 2 - 3 - 4 - ...

즉, 맨 앞에서 조사받은 숫자가 맨 뒤로 이동한다. 이를 일직선으로 나타내 보면, 다음과 같이 나타낼 수 있다.

 

 

 

 

조사를 받은 1이 맨 뒤로 이동한다.

 

이를 queue로 구현하면, 맨 앞 숫자를 꺼냈다가(pop) 그것이 빼내 지지 않는다면(k번째 사람이 아니라면)

다시 맨뒤로 push하면 된다.

 

 

2. 코드

#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n, k;
    cin >> n >> k;
    
    for (int i = 1;i <= n;i++) {        //순서대로 queue에 넣는다.
        q.push(i);
    }
    int turn = 1, cur, cnt = 0;            //cur : 현재 탐색받는 사람
    while (!q.empty()) {                //cnt : 출력 형식을 맞춰주기 위한 카운터
        cur = q.front();                //맨 앞의 사람을 queue에서 꺼내 탐색한다.
        q.pop();                        
        if (turn % k == 0) {            //k번째 사람이면
            cnt++;                          
            if (cnt == 1) {
                cout << '<';
            }
            cout << cur;                //이번에 죽은 사람을 출력한다.
            if (cnt == n) {
                cout << '>';
            }
            else {
                cout << ", ";
            }
        }
        else {                           //k번째 사람이 아니면
            q.push(cur);                //다시 queue의 맨 뒤로 넣어 준다.
        }
        turn++;    
    }
 
    return 0;
}

 

 

 

3. 나가며...

vector.erase()를 이용하면 해당 자리까지 깔끔하게 지워지기 때문에 vector로 구현하는 것도

그렇게 복잡하지는 않다.