11866 요세푸스 문제0

문제링크 : www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

 

---

---

<알고리즘>

  1) vector를 이용해 1~N까지의 숫자를 나열(1~N까지의 숫자를 0~N-1칸에 배열)

  2) index = K-1로 시작해 vector[index]값을 요세푸스 순열에 추가

  3) 이미 요세푸스 순열에 추가된 vector[index]값은 삭제

  4) index를 K-1값(도착지점 포함 K칸이니까)만큼 증가시키는데 배열의 size를 넘지않게 주의

  5) vector의 요소가 1개 남을 때까지(index변경 수식에서 zero division발생 방지) 2~4과정 반복

  6) 하나 남은 vector 요소를 요세푸스 순열에 추가

  7) 문제에서 요구하는 형식에 맞춰 queue 출력, pop 반복

 

 

 

메모리 : 2016KB       시간 : 0ms

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

int main() {
	int N = 0;
	int K = 0;
	cin >> N >> K;

	vector<int> member(N);
	for (int i = 1; i <= N; i++) { member[i - 1] = i; }
	queue <int> result;
	
	int index = K - 1;
	for (int i = 0; i < N; i++) {
		result.push(member[index]);
		member.erase(member.begin() + index);
		if (member.size() >1) {
			index = (index + K - 1 >= member.size()) ? (index + K - 1) % member.size() : (index + K - 1);
		}
		else {
			index = 0;
		}
	}

	cout << "<";
	while(result.size()>1){
		cout << result.front() << ", ";
		result.pop();
	}
	cout << result.front() << ">";
	return 0;
}