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

#문제

#풀이

#include <iostream>
#include <vector>

using namespace std;

vector<int> peoples;

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL);

	int N, K;
	cin >> N >> K;

	for (int i = 1; i <= N; ++i)
	{
		peoples.push_back(i);
	}

	int target = 0;

	cout << '<';
	while (!peoples.empty())
	{
		target += K - 1;
		target %= peoples.size();

		cout << peoples[target];
		peoples.erase(peoples.begin() + target);

		if (!peoples.empty())
		{
			cout << ", ";
		}
	}
	cout << '>';

	return 0;
}

#정리

주어진 N개의 원소를 K의 배수로 삭제한다. 7, 3이 주어졌다면 … 3, 6, 2(7>1>2), 7(4>5>7), 5, 1, 4 이런 식으로 넘어가면 1부터, 이미 삭제된 숫자라면 넘어간다. 주어진 N개만큼 vector의 원소를 초기화 후, vector가 empty가 아닌 동안 다음의 연산을 반복했다. target num에 K-1을 더해주고, vector의 크기로 나머지 연산을 하면서 출력. 출력된 숫자는 erase 메서드를 사용하여 지워줬다. **알고리즘 공부하면서 linked list로 해결한 경험이 생각났다. 그 때는 타겟 숫자를 삭제하면서, 앞 뒤 원소의 prev, next pointer를 변경해주며 해결했었다. 지금은 vector가 알아서 그 일을 해주니, 훨씬 편하게 문제를 해결할 수 있게 되었다.

#문제

#풀이

#정리

Enjoy Reading This Article?