algospot 조세푸스 문제 (문제 ID: JOSEPHUS) c++

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/JOSEPHUS

algospot.com :: JOSEPHUS

조세푸스를 포함해서 병사들이 원형으로 앉아 순서대로 죽는다.

첫번째 병사가 처음으로 죽으면, 시계방향으로 k번째 사람이 죽기를 반복하다가 조세푸스를 포함한 병사 하나만 살아 남았을때 죽는것을 멈춘다고 한다.

이렇게 조세푸스가 마지막 두명중 하나가 되기 위해서는 조세푸스는 첫번째 병사로부터 몇자리 떨어진 곳에 있어야 하는지 구하는 문제이다.

 

이 문제를 풀려면 요소들을 순회하면서 삭제하는 작업을 반복적으로 해야한다.

이때 우리는 다양한 곳에서 요소를 추가/삭제할때 상수시간복잡도를 가지는 연결리스트( list )를 활용할 수 있다.

배열( vector, int[] )의 경우 맨 뒤 이외의 위치에서 원소 추가/삭제를 수행할때 선형시간복잡도를 가진다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/18.%20linearDS/JOSEPHUS.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2