연결 리스트 - 조세푸스 문제

문제 : 조세푸스 문제 (난이도 : 下)

 

https://algospot.com/judge/problem/read/JOSEPHUS

 

 분석

문제 상황이 원형 리스트 상태이다. STL에선 원형 리스트를 지원하지 않으므로 약간의 변형을 통해 구현하면 쉽게 문제를 해결할 수 있다.

 

 구현

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)
	{
		// earse() 지운 원소의 다음 원소를 반환
		kill = survivors.erase(kill);
		if (kill == survivors.end()) kill = survivors.begin();
		n--;
		// k-1 번 다음 사람으로 옮긴다.
		for (int i = 0; i < k - 1; i++)
		{
			kill++;
			if (kill == survivors.end()) kill = survivors.begin();
		}
	}
	cout << survivors.front() << " " << survivors.back() << '\n';
}

int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		int n, k;
		cin >> n >> k;
		josephus(n, k);
	}
	return 0;
}

※ list로 구현했지만, vector로 구현해도 상관없다.