[알고리즘/C++] 요세푸스 순열 문제 Josephus problem

# 요세푸스 문제 Josephus problem

요세푸스 문제 Josephus problem 혹은 요세푸스 순열 Josephus permutation 이라고 합니다.

 

자연수 n, k ( k < n )이 있습니다.

n명이 동그랗게 앉아있을 때 임의의 한 명부터 순서를 세어 k번 째 사람을 제외합니다.

다음 사람부터 k번째 사람을 제외합니다.

이렇게 제외되는 사람의 순서가 요세푸스 순열이고,

마지막에 남는 (혹은 제외되는)사람을 구하는 문제가 요세푸스 문제입니다.

 

# 알고리즘 이해

n=5; k=3; 으로 가정합니다.

즉 다섯 명이 모여있고, 세 번째 순서일 때마다 제외합니다.

 

# 코드 예제

#include <stdio.h>
#include <queue>
using namespace std;
int main(){
	int n, k, x, res;
	queue<int> q;
	scanf("%d %d", &n, &k);
	
    // n명 번호를 부여하여 큐에 넣기
	for(int i=1; i<=n; i++){
		q.push(i);
	}
	
    // 요세푸스 순열 알고리즘
	while(!q.empty()){
		for(int i=1; i<k; i++){
			x = q.front();
			q.pop();
			q.push(x);
		}
		res=q.front();
		q.pop();
	}
	printf("%d", res);
	
	
	return 0;
}