#11866. 조세퍼스 문제

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

1. 문제 이해

 둥글게 앉은 n명의 사람을 m번씩 건너 뛴 후에 뽑아내 그 순서를 나열하는 문제입니다. 

2. 접근방법

 문제를 보고 순환큐를 사용하겠다고 마음먹었습니다. 큐의 성질을 잘 이해하고 있다면, 쉽게 풀 수 있는 문제!!

3. 문제 해결

전체적인 루틴을 설명 드리겠습니다.

 우선, while 반복문을 실행 합니다. 

이 루프를 빠져 나오는 조건!! 큐에 아무것이 없을때 이 루프를 빠져 나오게 하려 합니다. 저는 여기서 "front == rear" 이 조건을 이용해서 이 루프를 빠져 나오겠습니다.

다음으로, 규칙을 잘 보시면 m-1번을 건너 뛴 이후에 m번째 사람이 뽑히게 되는것을 확인할 수 있게됩니다. 저는 m-1번을, 즉, 건너뛰는 사람들을 rear 뒤로 보낼 것 입니다. 그 다음으로 m번째 사람을 뽑고 그 값을 기록합니다.

#include <stdio.h>
#define MAX 1000000
 
int qu[MAX];
int output[MAX];
int front =-1;
int rear =-1;
 
void push(int n) {
    qu[++rear] = n;
}
 
int pop() {
    if (front == rear) {
        return -1;
    }
    else {
        return qu[++front];
    }
}
 
int main() {
    int n, m;
    int i, cnt=0;
 
    scanf("%d %d", &n, &m);
    for (i = 1; i <= n; i++) {
        push(i);
    }
 
    while (front != rear) {
        for (i = 0; i < m - 1; i++) {
            push(pop());
        }
        output[cnt] = pop();
        cnt++;
    }
 
    printf("<");
    for (i = 0; i < n - 1; i++) {
        printf("%d, ", output[i]);
    }
    printf("%d>\n", output[i]);
}
 

※ 느낀점.

이 문제를 풀게 됨으로써 큐라는 자료구조를 이해할 수 있었습니다.