문제

조세퍼스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ M ≤ N ≤ 5,000)

출력

예제와 같이 조세퍼스 순열을 출력한다.

예제 입력/출력

코드

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

int main() {
	int n, m, idx = 0, cnt;
	vector<int> nums;

	scanf("%d %d", &n, &m);
	// nums 벡터 초기화: 1~n까지 순서대로 삽입
	for (int i = 1; i <= n; i++)
		nums.push_back(i);

	idx = m - 1;
	printf("<");
	while (nums.size() > 1) {
		printf("%d, ", nums[idx]);
		nums.erase(nums.begin() + idx);
		idx += m - 1;
		idx %= nums.size();
	}
	printf("%d>\n", nums[0]);

	return 0;
}

풀이

위 문제의 출력방식은 다른 문제들과 달리 <> 와 콤마(,)후 띄어쓰기를 해야하는 특이한 방식을 가져서 조금 더 조건을 주어야 한다.

위 문제의 알고리즘 아래와 같다.

1. 벡터(nums)에 n까지의 값을 차례대로 넣어준다.
2. <을 먼저 출력해주고 시작한다.
3. 인덱스에 해당 하는 값과 콤마&공백(, )을 출력해준다.
4. 방금 출력한 값을 제거한다.
5. 다음 인덱스( 현재인덱스+(m-1) 후 나머지값 )을 지정해준다.
6. 3-5번을 벡터(nums)에 원소가 하나 남을 때까지 반복한다.
7. 하나밖에 남지 않은 경우 나머지 값과 >를 출력해준다.

여기서 m-1번째인 이유는 다음 인덱스를 알기전에 이미 하나의 값을 출력후 지워렸기 때문에 m보다 하나 작은 값이 된다.

그림에서 보이듯이 현재위치는 그대로지만 이미 하나가 삭제 되었기 때문에 다음 인덱스까지의 간격은 하나가 줄어든 것이다.

또한 현재 백터의 원소개수로 나눠서 나머지 값을 인덱스로 사용하는 이유는, 인덱스 값이 벡터에 남아있는 원소의 개수보다 큰 경우를 방지하기 위함이다.

이 문제의 분류는 Queue(큐)에 속해있다.
위 방법은 큐를 사용한 방식은 아니지만, 큐로 사용하였을 때 방법은 아래와 같다.

1. front가 m의 배수번째가 아닌 경우, pop(제거)한 후 push_back(맨 뒤로 보낸다)을 한다.
2. m의 배수번째인 경우, pop(제거)하며 출력한다.
3. queue가 공백이 될때까지 1-2 번을 반복하여 실행한다.

여기서 m의 배수번째라 하면 m = 3일때,
3, 6, 9, … 번째에 위치해있는 값들을 의미한다.
m의 배수번째에 속하지 않은 값들을 차례대로 뒤에 보내게 되면 언젠가 출력하게 된다.