algospot JOSEPHUS

문제 링크입니다: https://algospot.com/judge/problem/read/JOSEPHUS

직접 Circular Linked List를 구현해서 하는 방법도 있지만 간편하게 list 헤더파일에서 지원하는 list를 이용하고 list.end()에 도달시 list.begin()으로 옮겨주어 원형 리스트처럼 동작하게 구현했습니다.

#include <iostream>

#include <list>

using namespace std;

 

void josephus(int N, int K)

{

        //리스트

        list<int> survivors;

       

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

                 survivors.push_back(i);

 

        //이번에 죽을 사람을 나타내는 포인터

        list<int>::iterator kill = survivors.begin();

        //두명만 살아 남을 때까지

        while (N > 2)

        {

                 //첫 번째 사람이 자살, erase()는 지운 원소의 다음 원소 반환

                 kill = survivors.erase(kill);

                 //원형 연결리스트 흉내

                 if (kill == survivors.end())

                         kill = survivors.begin();

                 N--;

                 //erase()는 지운 원소의 다음 원소 반환하므로 K-1번 다음 사람으로 옮긴다

                 for (int i = 0; i < K - 1; i++)

                 {

                         kill++;

                         //원형 연결리스트 흉내

                         if (kill == survivors.end())

                                 kill = survivors.begin();

                 }

        }

        cout << survivors.front() << " " << survivors.back() << endl;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 int N, K;

                 cin >> N >> K;

 

                 josephus(N, K);

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략