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

1. 문제이해

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

11866번: 요세푸스 문제 0

 

1번부터 N번까지의 사람이 원을 이루며 앉아있다.

정수 K가 주어질 때, 순서대로 K번째 사람을 제거하며, 남은 사람들로 해당 과정을 반복해나간다.

N명의 사람이 모두 제거될 때까지 해당 과정을 반복할 때, 제거되는 순서를 요세푸스 순열이라고 한다.

N과 K가 주어질 때, 요세푸스 순열을 구하는 것이 목표이다.

 

2. 문제풀이

 

이전에 풀이한 백준 1158번 요세푸스 문제와 완전히 동일한 문제이다.

(백준에 동일한 문제가 이름만 살짝 틀리게 올라오다니..🤔)

 

풀이방법 또한 동일하니, 자세한 풀이방법은 아래 포스팅을 참고하자.

https://beginnerdeveloper-lit.tistory.com/128

[C++] 백준 1158번 요세푸스 문제

 

 

 

3. 소스코드

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

int main() {
	vector <int> v;
	int N, K;
	int index;

	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		v.push_back(i);
	}

	cout << "<";

	index = (K - 1) % N;
	while (!v.empty()) {
		cout << v[index];
		v.erase(v.begin() + index);
		index += K - 1;

		if (v.empty()) {
			break;
		}

		if (index >= v.size()) {
			index = index % v.size();
		}

		cout << ", ";
	}

	cout << ">";

	return 0;
}

 

 

---

이제와서 보니 해당 문제는 큐를 사용하신 분들이 꽤나 많더라..

큐를 이용해 푸는 방법도 꽤나 간편해보이니, 조만간 한번 풀어봐야겠다.😊

 

문제에 대한 질문이나 지적은 언제나 감사하게 받고 있습니다.😊