11866 : 요세푸스 문제 (C)

11866번: 요세푸스 문제 0

---

- 1차 유대-로마 전쟁 당시 요세푸스(Flavius Josephus)는 동료 40명과 함께 로마군에게 포위됐다.

이들은 투항하는 대신, 제비를 뽑아 둥글게 둘러 앉은 후 두 명씩 건너 뛰고 세 번째마다 자살하기로 하였다.

이렇게 하여 39명이 죽은 뒤 요세푸스는 살아남은 동료 1명을 설득하여 투항했고,

훗날 역사가가 되어 이 일을 기록에 남겼다고 한다.

(치사한거 아닌가? 지 혼자만 살아남네)

 

여튼, 큐를 이용하여 풀 수 있는 문제이다.

먼저 큐의 맨 앞에 있는 두명을 맨 뒤로 보내고 맨 앞을 한명 죽이고를 반복하면 되는 문제.

예) 7명의 사람과 순서대로 3번째 사람을 제거할 때.

큐 - 1, 2, 3, 4, 5, 6, 7

1) 맨 앞의 두명을 맨 뒤로 보냄

  3, 4, 5, 6, 7, 1, 2

2) 맨 앞을 제거

  4, 5, 6, 7, 1, 2

3) 반복

 

#include<stdio.h>
#include<stdlib.h>

typedef struct {
    int data;
    struct Node *next;
} Node;

typedef struct {
    int count;
    Node *front;
    Node *rear;
} Queue;

void push(Queue *queue, int data) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    if(queue->count == 0) {
        queue->front = node;
    } else {
        queue->rear->next = node;
    }
    queue->rear = node;
    queue->count++;
}

int pop(Queue *queue) {
        Node *node = queue->front;
        int data = node->data;
        queue->front = node->next;
        free(node);
        queue->count--;
        return data;
}

int main() {
    Queue queue;
    queue.front = queue.rear = NULL;
    queue.count = 0;

    int personNumber, kill;
    scanf("%d %d", &personNumber, &kill);

    for(int i = 0; i < personNumber; i++) {
        push(&queue, i+1);
    }

    printf("<");

    while(queue.count != 0) {
        for(int i = 0; i < kill - 1; i++) {
        // 2명만 맨 뒤로 보내야 함.
            push(&queue, pop(&queue));
            // 맨 앞 사람을 뽑아 내는 동시에 뒤로 보냄
        }
        if(queue.count != 1) {
            printf("%d, ", pop(&queue));
        } else {
            printf("%d>", pop(&queue));
            // 한 명 남았을 때 괄호로 닫아 마무리한다.
        }
    }

    return 0;
}

연결리스트로 큐를 구현한 다음 문제를 해결하였다.

 

#include<stdio.h>

typedef struct {
    int data[1000];
    int front, rear;
} Queue;

void push(Queue *queue, int data) {
    queue->data[queue->rear++ % 1000] = data;
}

int pop(Queue *queue) {
    int data = queue->data[queue->front++ % 1000];
    return data;
}

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

    Queue queue;
    queue.front = queue.rear = 0;
 
    for(int i = 0; i < N; i++) {
        push(&queue, i + 1);
    }

    printf("<");

    while(queue.rear - queue.front != 0) {
        for(int i = 0; i < K - 1; i++) {
            push(&queue, pop(&queue));
        }
        if(queue.rear - queue.front != 1) {
            printf("%d, ", pop(&queue));
        } else {
            printf("%d>", pop(&queue));
        }
    }

    return 0;
}

구조체와 배열로 큐를 구현하여 푼 방식.

 

아래 방식이 연결리스트를 이용한 것이고, 위에가 배열을 이용하여 푼 방식이다.

 

이 문제는 최대 사람 수 가 5000명 까지 들어가는 요세푸스 문제이다.

배열을 이용하여 푼 것이 메모리와 시간을 덜 사용하는 것을 알 수 있다.