반응형
https://algospot.com/judge/problem/read/JOSEPHUS
algospot.com :: JOSEPHUS
조세푸스 문제 문제 정보 문제 1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 N - 1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하느니 차라리 자살하자고 결의했고, 포위당한 N명의 사람들이 모두 원형으로 둘러선 뒤 순서대로 자살하기로 했습니다. 한 사람이 자살하면, 다음에는 그 사람으로부터 시계 방향으로 K번째 살아 있는 사람이 자살하는 것입니다. 조세푸스의 책에 따르면 조세푸스와 다른 병사 하나
algospot.com
처음 입력 시 순서대로 넣어주기 때문에 sorting 할 필요가 없습니다. 그 다음 원소를 접근하는 개념으로써 자료구조 list가 적당합니다. vector로 사용하기엔 구현하기 어려운 문제였습니다. vector가 연속된 자료들의 집합이기 때문에 erase()함수를 쓰면 지운 다음 배열을 가르키기 때문에 만약 vector의 end()라면 반환값은 쓰레기 값이 들어가게 됩니다. 따라서 바로 다음 원소의 위치를 가르키고 있는 형태의 연결리스트 구조가 이 문제를 풀기 좋습니다.
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main() {
int c, n, k;
cin >> c;
while (c--)
{
cin >> n >> k;
list <int> p(n);
int cnt = 1;
for (auto it = p.begin(); it != p.end(); it++)
{
*it = cnt++;
}
int f = 0;
int die = 0;
list <int>::iterator pre = p.begin();
list <int>::iterator cmp;
while (p.size() != 2)
{
pre = p.erase(pre);
if (pre == p.end())pre = p.begin();
for (int i = 0; i < k - 1; i++) {
pre++;
if (pre == p.end())pre = p.begin();
}
}
for (auto it = p.begin(); it != p.end(); it++)
{
cout << *it << ' ';
}
cout << '\n';
}
}