[BOJ 11866, 1158, 11025/C++] 요세푸스 문제 시리즈

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

11866번: 요세푸스 문제 0

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

1158번: 요세푸스 문제

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

11025번: 요세푸스 문제 3

 

요세푸스 문제는 n명의 사람이 원형으로 앉아있을 때, k번째 사람을 제거하고 남은 사람들끼리 해당 과정을 반복해 n명의 사람이 모두 제거 될 때까지 이를 반복해 나간다. 

 

요세푸스 문제 0, 요세푸스 문제 풀이

1. queue를 이용한 풀이(naive)

 단순히 생각해보았을 때, 배열 안의 원소를 pop, push를 반복하다가 k번째로 pop 되는 원소는 출력하고 다시 push 하지 않는 것을 가장 naive한 풀이로 생각해볼 수 있다. queue의 FIFO 특성을 이용한 가장 naive한 풀이라고 생각이 든다.

#include <iostream>
#include <queue>

using namespace std;

int N, K, cnt;
queue<int> qu;

int main() {
	cin >> N >> K;

	for (int i = 1; i <= N; i++) {
		qu.push(i);
	}
	cnt = 1;
	cout << '<';
	while (qu.size()) {
		if (cnt != K) {
			qu.push(qu.front());
			qu.pop();
			cnt++;
		}
		else { //K번째 원소인 경우
			if (qu.size() - 1 != 0) cout << qu.front() << ", ";
			else cout << qu.front() << ">";
			qu.pop();
			cnt = 1;
		}
	}
}

2. vector를 이용한 풀이

queue에서 원소를 pop하고 다시 push하는 것에 대해서 굳이 그렇게 할 필요가 있나..?하는 생각이 들었다. vector에서 index를 활용하면 원소를 움직이는 대신에 index가 움직이면서 k번째 원소를 찾을 수 있다는 생각이 들었고 같은 O(n^2) 풀이지만 더 짧은 시간 안에 문제를 해결할 수 있었다. k번째 원소에 해당하는 원소는 erase 해서 vector에서 삭제하고, index에 k를 더해 다음 index를 찾을 수 있도록 한다. 이 때, index가 vector의 크기를 넘으면 안되기 때문에 현재 vector의 크기로 나눈 나머지를 index에 대입해 다음 원소를 찾을 수 있다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, k, i;
	vector<int> v;
	cin >> n >> k;
	
	for (i = 1; i <= n; i++) {
		v.push_back(i);
	}

	i = k-1;
	cout << "<";
	while (v.size() != 1) {
		cout << v[i]<<", ";
		v.erase(v.begin() + i);
		i += k-1;
		if (i >= v.size()) i %= v.size();
	}
	cout << v[0] << '>';
}

 

위의 두 방법 모두 O(n^2)의 시간 복잡도를 가지는데, 세그먼트 트리나 이진탐색트리를 이용하면 O(nlogn)의 시간복잡도를 통해 문제를 풀 수 있다고 한다.

---

요세푸스 문제 3 풀이

이번 문제에서는 요세푸스 순열이 아니라 제일 마지막에 남은 수만 구하는 문제이다. 

여기서 f(n, k)를 제일 마지막에 남는 수라고 하자.

 

예를 들어 f(7, 3)을 구하기 위해서 우리는 1에서 7이 들어간 queue에서 제일 처음 3을 제거해 다음과 같은 순열을 얻는다.

3을 제거하고 남은 원소

그 다음으로 우리는 다시 한번 값을 4와 5를 뒤로 보내고 6을 제거하는 일을 하게 된다. 이는 f(6,3)에서의 첫번째 원소를 없애는 것과 동일한 연산임을 알 수 있다.

그렇다면 이 때, 각각의 값을 f(6,3)의 첫단계와 대응시켜보면 어떨까?

각각의 원소들은 queue X는 f(7,3)의 두번째 단계, queue Y는 f(6,3)의 첫번째 단계를 보여주는 queue라고 하면

모든 i에 대해서 X의 원소들은 X[i] = (Y[i]+3)%7 로 나타낼 수 있으며, 그 대응은 다음과 같다.

그렇다면 우리는 f(7,3)에 해당하는 원소에 대해서도 마찬가지임을 알 수 있고

위와 같은 식을 얻을 수 있다. 이를 일반화하면

의 식을 얻을 수 있고, bottom-up 방식을 통해 f(n, k)를 구하면 O(n)의 시간복잡도를 가지고 이 문제를 해결할 수 있다.

 

#include <iostream>
using namespace std;

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

	int ans = 0;
	for (int i = 2; i <= n; ++i) {
		ans = (ans + k) % i;
	}
	cout << ans + 1;
}