알고스팟: 조세푸스 문제 (ID: JOSEPHUS)

[문제 링크]

algospot.com :: JOSEPHUS

---

연결 리스트인 list 컨테이너를 활용하여 풀 수 있는 간단한 문제였다.

 

erase() 함수를 수행하면 다음 원소의 반복자를 반환하므로, erase() 후 K-1 만큼 반복자를 이동시킨 다음 반복자가 가리키는 원소를 erase() 하여 최종적으로 2명이 남게되면 결과를 출력하도록 구현하였다.

 

추가적으로 반복자가 list 의 끝에 도달했을 때 ++ 연산으로 첫번째 원소를 가리킬 수 없으므로, begin()을 통해 list의 첫번째 원소를 가리키도록 해주었다.

---

#include <iostream>
#include <list>
using namespace std;

int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		int N, K;
		cin >> N >> K;

		list<int> soldier;
		for (int i = 1; i <= N; i++)
			soldier.push_back(i);

		list<int>::iterator iter = soldier.begin();

		iter = soldier.erase(iter);

		while (soldier.size() > 2)
		{
			for (int i = 1; i < K; i++)
			{
				iter++;
				
				if (iter == soldier.end())
					iter = soldier.begin();
			}

			iter = soldier.erase(iter);

			if (iter == soldier.end())
				iter = soldier.begin();
		}

		cout << soldier.front() << ' ' << soldier.back() << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 136 day