[알고리즘/문제풀이/BOJ 11866번] 요세푸스 문제 0

요세푸스 문제 0은 큐를 활용하여 풀 수 있는 문제이다. 사람들이 큐에서 K-1번 쉬프트 로테이션을 한 후 pop을 하여 사람의 번호를 추출함으로써 해결할 수 있다.

작성한 코드는 다음과 같다.

---

#include<stdio.h>
#define size 2000
//http://ark-hive.tistory.com/
//사람들이 큐에서 쉬프트로테이션을 하면 어떻게 될까?
int N, K;

int queue[size];

int head, tail;

int pop() {
	head += 1;
	head %= size;
	return queue[(head +size - 1)%size];
}

void push(int x) {
	queue[tail] = x;
	tail += 1;
	tail %= size;
}

int main(void) {
	scanf("%d %d", &N, &K);

	for (int i = 1; i <= N; i++) {
		push(i);
	}

	printf("<");
	while (head != tail) {
		for (int i = 0; i < K-1; i++)
			push(pop());
		printf("%d", pop());
		if (head != tail) {
			printf(", ");
		}
	}
	printf(">");
}

문제의 지문은 다음 링크에서 확인할 수 있다.

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