[자료구조 알고리즘] 17413

자료구조 queue, stack 관련 백준 문제 풀이들.

중간고사 대비로 풀었던거 하나하나 정리할 차례다.. 귀찮아서 미뤄둔걸 학기가 다 끝난 이제서야 올린다.

 

1. 17413  요세푸스 순열

 

위키백과 정의에 따르면 요세푸스 순열은 다음과 같다. n과 k가 자연수이고, k < n이라고 가정한 상태에서, n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.

 

문제를 푸는 main idea는 어떤 자료구조를 사용할 것이냐인데 딱 봐도 그냥 무난한 queue가 좋을 것 같이 생겼다.

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

int main() {
	int n, m;
	cin >> n >> m; //n사람 m순서
	queue<int> que;

	for (int i = 1; i <= n; i++) {
		que.push(i);
	}

	cout << "<";
	
	while (que.size()>1) {
		for (int i = 1; i < m; i++) {
			que.push(que.front());
			que.pop();
		}
		cout << que.front() << ", ";
		que.pop();
	}
	cout<<que.front();
	que.pop();
	cout << ">";

	return 0;
}