BOJ 11866 조세퍼스 문제0

조세퍼스 문제는 다음과 같다.

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

N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.

---

circular queue를 이용했다.

1~N까지 큐에 입력 후 M만큼 뒤로 보내고, 하나 출력시마다 front +1 하는 식으로 front를 조정했다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

// 11866 조세퍼스 문제0 #include<stdio.h> #define FOR(i,j) for(int i=1;i<=j;i++) #define MAX 1001 int main() { int N, M; int queue[MAX] = { 0, }; int adj[MAX] = { 0, }; int front, back; FOR(i, MAX-1) { queue[i] = i; } scanf("%d %d", &N, &M); front = 1, back = N; FOR(i, N) { FOR(j, M-1) { back %= N; back++; queue[back] = queue[front]; front %= N; front++; } adj[i] = queue[front]; front %= N; front++; } printf("<"); FOR(i, N - 1) printf("%d, ", adj[i]); printf("%d>", adj[N]); }

1158 조세퍼스 문제는 위 문제와 똑같으므로 생략하겠다. MAX의 범위만 고쳐주면 된다.