[C++] 백준 1168번 - 요세푸스 문제 2

---

0. 문제

 

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

 

1. 아이디어

 

1) 1번부터 N번까지, 총 N명의 사람을 vector에 삽입하고 순서대로 K번째 사람을 탐색해가면서 vector에서 제거하고 다음 K번째 사람을 탐색하는 과정을 반복한다.

 

2) 이때 K번째 사람을 찾는다고 해서 index의 값을 +k 한다고 생각할 수도 있지만 그렇지 않다.

이미 앞전의 과정에서 하나의 원소를 vector에서 제거했기 때문에 결과적으론 +k-1 하면 된다!

 

2. 소스코드

 

#include <iostream>
#include <vector>
int main()
{
	int K, N;
	std::cin >> N >> K;

	std::vector<int> v(N);
	std::vector<int> result;

	for (int i = 0; i < N; i++) v[i] = i + 1;
	
	int idx = 0;
	while (!v.empty())
	{
		idx = (idx + K - 1) % v.size();
		result.push_back(v[idx]);
		v.erase(v.begin() + idx);
	}
	std::cout << "<";
	for (int i = 0; i < N; i++)
	{
		std::cout << result[i];
		if (i < N - 1) std::cout << ", ";
	}
	std::cout << ">";
	return 0;
}

 

3. 결과

 

 

4. 피드백

 

• 이제 슬슬 시험기간이라 알고리즘 공부하기가 쉽지 않다 ㅜㅜ

---