[Baekjoon/C++] 1158번 - 요세푸스 문제

[백준] Baekjoon Online Judge

문제로 이동

 

문제

요세푸스 문제는 다음과 같다.

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

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

 

출력

예제와 같이 요세푸스 순열을 출력한다.

 

---

예제 입력	예제 출력
7 3	<3, 6, 2, 7, 5, 1, 4>

---

풀이

#include <iostream>
using namespace std;

struct queue {
    int arr[5001];
    int front, rear;
};

int N, K; // N명의 사람, K번째 사람
int numArr[5001];
queue q;

void init();
void enqueue(int n);
int dequeue();
void print();

// 큐 초기화
void init() {
    q.front = q.rear = 0;

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

// 삽입 함수
void enqueue(int n) {
    q.rear = (q.rear + 1) % N;
    q.arr[q.rear] = n;
}

// 삭제 함수
int dequeue() {
    q.front = (q.front + 1) % N;

    return q.arr[q.front];
}

// 출력
void print() {
    printf("<%d", numArr[0]);
    for (int i = 1; i < N; i++) printf(", %d", numArr[i]);
    printf(">\n");
}

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

    init();

    // 순서대로 K번째 사람을 제거
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < K - 1; j++) enqueue(dequeue());

        numArr[i] = dequeue();
    }

    print();

    return 0;
}

원형큐를 사용해서 문제를 풀었다.

 

struct queue {
    int arr[5001];
    int front, rear;
};

int N, K; // N명의 사람, K번째 사람
int numArr[5001];
queue q;

일단 데이터와 front, rear을 가지고 있는 queue 구조체를 만들었다. 

numArr[]는 제거된 사람들의 번호를 순서대로 저장하는 배열이다.

 

// 큐 초기화
void init() {
    q.front = q.rear = 0;

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

큐를 초기화하는 함수이다. front와 rear을 0으로 초기화하고, 큐에 N만큼의 번호를 넣는다.

 

// 삽입 함수
void enqueue(int n) {
    q.rear = (q.rear + 1) % N;
    q.arr[q.rear] = n;
}

// 삭제 함수
int dequeue() {
    q.front = (q.front + 1) % N;

    return q.arr[q.front];
}

삽입/ 삭제 함수이다. 원래는 여기에 큐가 가득 찼는지, 비었는지를 확인하는 if문이 들어가야 하지만 해당 문제에서는 빈 큐의 숫자를 삭제하거나 가득찬 큐에 숫자를 삽입하는 경우가 없기에 이를 포함하지 않았다.

 

// 출력
void print() {
    printf("<%d", numArr[0]);
    for (int i = 1; i < N; i++) printf(", %d", numArr[i]);
    printf(">\n");
}

주어진 출력형식에 맞게 답을 출력하는 함수이다.

 

    // 순서대로 K번째 사람을 제거
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < K - 1; j++) enqueue(dequeue());

        numArr[i] = dequeue();
    }

main함수에서 순서대로 K번째 사람을 제거하는 코드이다. 삽입과 삭제를 반복하다 필요한 사람이 나오면 이를 나중에 출력에 사용하기 위해 numArr[]에 저장한다.