[Algospot]알고스팟 조세푸스 문제 풀이

환형 링크드리스트 개념 이용 / 비교적 쉽게 해결할 수 있었음(시간복잡도 계산 시 O(N*K) 정도?)

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
/*
<문제> 시간 1초, 메모리 65536kb
조세푸스와 N-1명의 사람(총 N명)이 동그랗게 서서
임의의 한 명이 죽고 시계방향으로 K 번째 살아있는 사람 자살
조세푸스와 다른 병사 하나가 살아남기 위해 조세푸스는 첫번째 병사로부터 몇자리 떨어진 곳에 있어야 할까?
 
<입력>
C    (testcase)
N K    (둘다 <=1000 / N은 3, K는 1부터 시작)
 
<출력>
마지막 살아남는 두 사람의 번호를 오름차순으로 출력
(첫번째 자살하는 병사 번호가 1, 다른사람은 이 사람에서 시계방향으로 정해짐
 
<풀이>
환형 링크드리스트 개념 이용 / 가장 끝사람 다음은 가장 첫 사람으로 연결시켜 놓고, 죽이기 진행
*/
 
struct Person {
    int num;    //병사 번호
    Person* next;    //다음병사 위치
    Person* prev;    //이전병사 위치
};
 
int Size = 0;    //사람 수
int main() {
 
    int c; cin >> c;
    while (c--) {    //testcase
        int n, k; cin >> n >> k;    //사람 수, K번씩 이동
        Size = n;    //사람 수
        Person* first = new Person();    //첫번째 병사
        first->num = 1;
        Person* prevPerson = first;    //이전 사람 위치
        for (int i = 2; i <= n; i++) {
            Person* a = new Person();
            a->num = i;     prevPerson->next = a; a->prev = prevPerson; // 번호지정 및 이전사람과 연결
            if (i == n) {    //마지막 사람인 경우 -> 다음사람을 first로 연결
                a->next = first; first->prev = a;
            }
            prevPerson = a;    //이전사람 업데이트
        }
        //병사들 원형으로 세우기 끝
 
        Person* killman = first;    //죽을사람
        Person* ans = first;    //나중에 출력할때 쓸 사람
        while (Size > 2) {    //2명 남을때까지 죽일거    
            Person* nextKillman = killman->next;//다음에 죽을 사람
            //killman 죽이기
            killman->next->prev = killman->prev;
            killman->prev->next = killman->next;
            Size--;
            for (int i = 0; i < (k - 1) + Size % Size; i++)     //k번 이동(nextKillman 선정) - Size보다 크면 나눈 나머지만큼만 이동하면 됨
                nextKillman = nextKillman->next;
            killman = nextKillman;
        
        }
 
        if (killman->num < killman->next->num) //오름차순으로 출력
            cout << killman->num << " " << killman->next->num << endl;
        else
            cout << killman->next->num << " " << killman->num << endl;
 
    }
    return 0;
}