조세푸스 문제

문제링크: 조세푸스 문제

원형으로 원소를 삭제하는 문제이다. 

벡터나 c++라이브러리에서 지원하는 벡터나 리스트를 이용하면 간단히 되지만 다른 라이브러리를 사용하지 않으려고 링크드리스트를 만들어 사용해 보았다. 

- 원형 리스트를 이용한 구현

#include <iostream>
using namespace std;
int C, N, K;
 
typedef struct list {
    int elem;
    list *prev;
    list *next;
} List;
 
List *list;
 
List* addNode(List *head, int elem) {
    List *node = (List*)malloc(sizeof(List));
    node->elem = elem;
    head->next = node;
    node->prev = head;
    node->next = NULL;
    return node;
}
void printList(List *head) {
    for (int i = 0; i < N; i++) {
        cout << head->elem << " ";
        head = head->next;
    }
    cout << endl;
}
 
List* removeNode(List* node) {
    List* nextNode;
    node->prev->next = node->next;
    node->next->prev = node->prev;
    nextNode = node->next;
    free(node);
    return nextNode;
}
void solve() {
    // 첫노드
    List *head = (List*)malloc(sizeof(List));
    head->elem = 1;
    head->prev = NULL;
    head->next = NULL;
 
    List *tmp = head;
    for (int i = 2; i <= N; i++) {
        tmp = addNode(tmp, i);
        if (i == N) {
            tmp->next = head;
            head->prev = tmp;
        }
    }
    // printList(head);
    tmp = removeNode(head);
    for (int i = 0; i < (N - 3); i++) {
        for (int j=0; j < (K-1); j++) {
            tmp = tmp->next;
        }
        tmp = removeNode(tmp);    
    }
    int result[2];
    for (int i = 0; i < 2; i++) {
        result[i] = tmp->elem;
        tmp = tmp->next;
    }
    if (result[0] > result[1])
        swap(result[0], result[1]);
    cout << result[0] << " " << result[1] << endl;
}
int main() {
    freopen("input.txt", "r", stdin);
    cin >> C;
    for (int c = 0; c < C; c++) {
        cin >> N >> K;
        solve();
 
    }
    return 0;
}

- 최적화된 해법 (dp 이용)

K-1번 포인터를 옮기는 대신, (K-1) mod N번 포인터를 옮기는 것이다. 

N명이 남아있을 때, N번 포인터를 옮기면 결국 자기 자신으로 돌아오기 때문이다. 

아래와 같이 dp로 풀 수 있다. 

0, 1 두명이 남았을 때부터 시작해서 N명이 남았을 때, 두명의 index를 찾는 것으로 풀어나가면 된다. 

이해가 쉽지는 않음.. 

#include <iostream>
 
using namespace std;
 
int main()
{
    int C;
    cin >> C;
    while (C--)
    {
        // j: last survivor, k: second-last survivor
        int j, k, N, K;
        cin >> N >> K;
 
        // recurrence relation: j(n, k) = { j(n-1, k) + (k-1) } % (n-1) + 1
        j = 0, k = 1;
        for (int i = 2; i < N; i++)
        {
            j = (j + (K-1)) % (i) + 1;
            k = (k + (K-1)) % (i) + 1;
        }
 
        cout << min(j, k) + 1 << " " << max(j, k) + 1 << endl;
    }
 
    return 0;
}