[백준/C++] 11866번: 요세푸스 문제 0

문제

https://www.acmicpc.net/problem/11866

---

문제 요약

1번부터 n번까지 n명의 사람이 원을 이루면서 앉아있다.

 

양의 정수 k가 주어졌을 때, 순서대로 k번째 사람을 제거한다.

 

한 사람이 제거되면, 남은 사람들로 이루어진 원을 따라 과정을 계속한다.

 

위 과정을 n명의 사람이 모두 제거될 때까지 계속한다.

 

원에서 사람들이 제거되는 순서를 요세푸스 순열이라고 한다.

 

형식에 맞게 요세 푸스 순열을 출력한다.

---

코드

#include <iostream>
#include <vector>

using namespace std;

int n, k;

vector<int> v, res;

int main() {
	
	cin >> n >> k;

	// 1번 ~ n번 삽입
	for (int i = 1; i <= n; i++) {
		v.push_back(i);
	}

	int idx = 0;

	// k번째 요소를 지워가며 res에 삽입
	for (int i = 0; i < n; i++) {
		idx = (idx + (k - 1)) % v.size();
		res.push_back(v[idx]);
		v.erase(v.begin() + idx);
	}

	// res 출력
	cout << "<" << res[0];
	for (int i = 1; i < n; i++) {
		cout << ", " << res[i];
	}
	cout << ">";

	return 0;
}

---

코드 설명

1. 벡터 v에 1부터 n까지 삽입하여 원형 큐를 구현한다.

(%연산자를 사용하면 원형 큐처럼 사용할 수 있다.)

 

2. idx 포인터를 이용해 k번째 요소를 하나씩 빼고 res 벡터에 순서대로 삽입한다.

 

3. res 벡터를 형식에 맞게 출력한다.

---

고찰

벡터의 idx번째 요소를 지우고 싶다면, erase 함수를 사용하면 된다.

v.erase(v.begin() + idx);