조세푸스 문제(JOSEPHUS) 정답 코드

문제를 보시려면 여기를 클릭

이하는 코드입니다.

#include <stdio.h>
 
#pragma warning(disable:4996)
 
typedef struct Person {
    int id;
    struct Person *next;
} Person;
 
typedef struct {
    Person *last;
    Person *beforeTarget;
    int size;
} List;
 
List *list;
int N, K;
 
void pushBack(int id) {
    Person *newPerson = new Person;
    newPerson->id = id;
    
    if (list->size == 0) {
        newPerson->next = NULL;
    }
    else if (list->size == 1) {
        newPerson->next = list->last;
        list->last->next = newPerson;
    }
    else {
        // new person -> first
        Person *first = list->last->next;
        newPerson->next = first;
 
        // old last -> new person
        list->last->next = newPerson;
    }
 
    // new last = new person
    list->last = newPerson;
 
    list->size++;
}
 
void killTarget() {
    if (list->size <= 2) {
        return;
    }
 
    Person *target = list->beforeTarget->next;
    
    // before target -> target's next
    list->beforeTarget->next = target->next;
 
    // set list's beforeTarget
    Person *temp = list->beforeTarget;
    for (int i = 0; i < K - 1; i++) {
        temp = temp->next;
    }
    list->beforeTarget = temp;
 
    // remove target
    delete(target);
    list->size--;
 
    // recursive call
    killTarget();
}
 
int main() {
    int C;
    scanf("%d", &C);
 
    for (int i = 0; i < C; i++) {
        scanf("%d %d", &N, &K);
 
        list = new List;
        list->size = 0;
        
        for (int j = 0; j < N; j++) {
            pushBack(j + 1);
        }
 
        list->beforeTarget = list->last;
        killTarget();
 
        int id1 = list->beforeTarget->id;
        int id2 = list->beforeTarget->next->id;
 
        if (id1 < id2) {
            printf("%d %d\n", id1, id2);
        }
        else {
            printf("%d %d\n", id2, id1);
        }
 
        delete(list);
    }
 
    return 0;
}