[1168번] 조세퍼스 문제 2

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 원형 큐 :: http://www.crocus.co.kr/283

2. 벡터(vector STL) :: http://www.crocus.co.kr/search/%EB%B2%A1%ED%84%B0?page=2

아래 소스 코드를 이해하기 위해서는 원형 큐 방식 및 벡터의 erase에 대한 개념이 필요하다.

물론 이 두가지를 이용하여 해결하는 것 외에 많은 방식이 있겠지만, 필자는 아래의 방식으로 해결하였다.

조세퍼스 문제는 해당하는 k번째의 사람을 지우면서 한명도 남지 않을 때 까지 반복하는 문제이다.

따라서 벡터를 이용하여 원형 큐 처럼 생각하였고, 해당하는 사람을 지울 땐 vector STL의 erase 함수를 이용하였다.

erase(vc.begin() + pos)의 의미는 해당하는 pos번째 벡터를 지운다는 의미이고 그 값을 지우는 순간

벡터에서는 뒤에 있는 값을 앞으로 당기기 시작한다.(벡터와 배열은 공간 할당이 동적인것 외에는 같은 방식으로 동작한다.)

코드의 주석을 통해 나머지 방식을 이해해보자.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int main()
{
    int n, m;
 
    scanf("%d %d", &n, &m);
 
    vector<int> vc(n);
 
    // 순열 입력
    for (int i = 0; i < n; i++)
        vc[i] = i + 1;
 
    // 현재 위치
    int pos = 0;
 
    printf("<");
    while (vc.size() != 1)
    {
        // 벡터의 원리에 의해 지워지면 당겨지니
        // m - 1번째 사람을 계속 없애면 된다.
        pos += m - 1;
 
        // pos가 vc크기를 넘어가면 원형 큐처럼 %를 이용한다. 
        if (pos >= vc.size())
            pos %= vc.size();
 
        // 해당하는 값을 출력하고 지워준다.
        printf("%d, ", vc[pos]);
        vc.erase(vc.begin() + pos);
    }
 
    // 마지막 사람을 출력한다.
    printf("%d", vc[0]);
    printf(">");
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>