백준 1158,11866-요세푸스 문제, 요세푸스 문제 0(C++)

문제 링크 : https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

문제

 

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

 

 

 

해설

원형을 구현하여야 한다.
원형은 선형을 이용해서도 구현할 수 있는데
방법은 선형을 처음부터 탐색하다 마지막까지 도달하면 다시 처음으로
돌아가는 것이다. 이렇게 되면 원형과 같아진다.

 

원형처럼 된다.

이는 배열을 이용하여 구현할 수 있지만 큐를 이용하는 것이 더 편하다.
아래에서 두 가지 경우의 코드를 모두 보여줄 것이다.

 

☆1158번 문제와 11866번 문제는 입력값의 범위만 다르고 나머지는 같은데
입력값이 크게 차이 나지 않기 때문에 같은 코드로 둘다 풀린다.

그래서 같이 해설한다.

 

 

코드(큐)

#include<iostream>
#include<queue>
using namespace std;
int main()
{
    int n,k,q=0;
    cin>>n>>k;
    int a[n];
    queue<int> v;
    for(int i=1; i<=n; i++)
        v.push(i);
    while(!v.empty())
    {
        for(int i=0; i<k-1; i++)
        {
            int w=v.front();
            v.pop();
            v.push(w);
        }
        a[q++]=v.front();
        v.pop();
    }
    cout<<'<';
    for(int i=0; i<n-1; i++)
    {
        cout<<a[i]<<", ";
    }
    cout<<a[n-1]<<'>';
}
//큐 사용

큐는 FIFO(First In First Out)의 형태를 가지고 있다.큐를 탐색할 때 나온 값을 다시 큐에 집어 넣으면 원형이 유지가 된다.

사람을 제거할 때만 다시 넣지않고 제거만 하면 된다. 이렇게 제거된 값만 따로 저장해두었다가

나중에 모두 형식에 맞춰 출력해준다. 

 

 

 

코드(배열)

#include<iostream>
using namespace std;
int main(void)
{
    int n,k;
    cin>>n>>k;
    int a[n],aa=-1;;
    for(int i=0; i<n; i++)
        a[i]=i+1;
    cout<<'<';
    for(int i=0; i<n; i++)
    {
        for(int z=0; z<k; z++)
        {
            aa++;
            if(aa==n)
                aa=-1;
            if(a[aa]==0)
                z--;
        }
        if(i!=n-1)
        {
            cout<<a[aa]<<", ";
            a[aa]=0;
        }
        else
            cout<<a[aa]<<'>';
    }
}
//배열 사용

배열을 이용해 원형을 구현하려면 배열을 탐색하다 끝에 도달하면 처음 인덱스로 돌아가면 된다. 이는 16~17행에 구현되어 있다. 제거된 숫자는 0으로 나타내어 준다. 탐색시 0을 만나면 제거된 것이므로 다시 탐색한다.

이는 18~19행에 구현되어 있다.