[백준 11866] 요세푸스 문제0

문제 풀이

 

빙글빙글 돌면서 K번째 사람을 퇴출하는 방식으로 뽑아내면 되는 문제입니다.

 

N = 7, K = 3이면

1, 2, 3, 4, 5, 6, 7 사람 중에서 3번째 사람을 뽑는 방식으로 진행합니다.

 

아래의 빨간 표시는 퇴출하는 사람의 순서입니다.

퇴출하고 나서 다음부터 다시 카운트를 시작합니다.

1

2

3

4

5

6

7

<3, 

1

2

3

4

5

6

7

<3, 6,

1

2

3

4

5

6

7

<3, 6, 2,

1

2

3

4

5

6

7

<3, 6, 2, 7,

1

2

3

4

5

6

7

<3, 6, 2, 7, 5, 

1

2

3

4

5

6

7

<3, 6, 2, 7, 5, 1, 

1

2

3

4

5

6

7

<3, 6, 2, 7, 5, 1, 4>

 

이러한 원리로 뽑으려면 앞에서 뽑고 뒤에서 넣는 형태이기 때문에, 큐 자료구조를 이용하면 쉽게 구현할 수 있습니다.

K = 3이면 1, 2번은 뽑아서 다시 뒤에 넣고, 3번째는 뽑아서 출력하고 큐에서 지워주면 됩니다.

 

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, k;
	cin >> n >> k;
	queue<int> q;
	for (int i = 1; i <= n; i++) q.push(i);

	vector<int> ans;
	while (!q.empty())
	{
		for (int i = 0; i < k - 1; i++)
		{
			q.push(q.front());
			q.pop();
		}
		ans.emplace_back(q.front());
		q.pop();
	}

	cout << "<";
	for (int i = 0; i < ans.size() - 1; i++)
	{
		cout << ans[i] << ", ";
	}
	cout << ans[ans.size() - 1] << ">\n";
	return 0;
}