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

1. 문제이해

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

1158번: 요세푸스 문제

 

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

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

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

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

 

 

 

2. 문제풀이

 

N명의 사람들을 K번째 사람씩 제거해나갈 때, 제거되는 순서를 구하는 것이 목표이다.

예제 입력 1에 대한 아래 풀이를 보자.

 

 

위와 같이 K - 1번째 원소를 순서대로 지워나가는 방식으로 풀이한다.

(배열이므로 index = K -1 부터 시작한다.)

K - 1 번째 원소를 삭제한 뒤, 기존 삭제된 index 값에 (K - 1) 값을 더해준다.

그러면 해당 index 값이 가리키는 값이 다음으로 삭제해야 하는 값이 된다.

즉, index = index + (K - 1) 이다.

 

이런식으로 기존 index 값에 (K - 1) 값을 더해나가며 삭제해주면 된다.

단, 배열의 사이즈 < index 인 경우를 주의해야 한다.

위와 같은 경우, 원 형태로 둘러앉았으므로, 인덱스값을 배열의 사이즈로 나눈 나머지를 구하면 된다.

즉, index = index % 배열의 사이즈 가 된다.

 

위와 같은 방법을 토대로 작성한 코드는 아래와 같다.

 

 

 

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;
}

 

N과 K를 입력받고, 벡터를 이용해 N 까지의 자연수를 저장한다.

2. 문제풀이에서 도출한 방식에 따라, 인덱스값을 기준으로 index += K - 1 을 해나가며

해당 값을 출력 후 삭제한다. (삭제되는 순서를 구하는 것이므로, 삭제되는 순서대로 바로 출력)

배열의 사이즈보다 인덱스 값이 큰 경우, index = index % 배열의 사이즈

이를 모든 값이 삭제될 때까지(v.empty()) 반복한다.

 

 

---

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