[백준] 11866번 : 요세푸스 문제 0 (C++)

 

---

문제

---

풀이

 요세푸스 문제는 큐(Queue)를 이용해 풀이할 수 있다.

 

1. queue를 사용하기 위한 헤더 파일을 추가한다.
2. 큐에 1부터 n까지의 원소를 넣는다.

#include <queue>	// queue를 이용하기 위한 헤더 파일
	int n, k;
	queue<int> q; // queue 선언

	cin >> n >> k;
	for (int i = 1; i <= n; i++) {	// 큐에 1부터 n까지 원소 넣기
		q.push(i);
	}

 

  3. 1부터 k-1까지의 원소를 큐의 뒤로 보내고, 삭제한다.

  4. k번째 원소를 출력한다.

  5. 만약, 큐의 크기가 2 이상이라면, ", "를 출력한다.

  6. k번째 원소를 삭제한다.

 

  7. 큐에 원소가 없어질 때까지, 3부터 6의 과정을 반복한다!  

 

	while (q.empty() == 0) { // 큐에 원소가 있다면,
		for (int i = 1; i < k; i++) { // 1부터 k-1까지의 원소를
			q.push(q.front()); // 큐의 가장 뒤로 보내고
			q.pop(); // 삭제한다.
		}
		cout << q.front(); // 가장 앞에 남은 k번째 원소를 출력한다.
		
		if (q.size() >= 2) { // 만약, 큐의 크기가 2 이상이라면,
			cout << ", "; // ", "를 붙인다.
		}
		q.pop();	// k번째 원소를 삭제한다!
	}

 

---

코드

#include <iostream>
#include <queue>

using namespace std;

int main() {
	int n, k;
	queue<int> q;

	cin >> n >> k;
	for (int i = 1; i <= n; i++) {	// 큐에 1부터 n까지 원소 넣기
		q.push(i);
	}
	
	cout << "<";

	while (q.empty() == 0) { // 큐에 원소가 있다면,
		for (int i = 1; i < k; i++) { // 1부터 k-1까지의 원소를
			q.push(q.front()); // 큐의 가장 뒤로 보내고
			q.pop(); // 삭제한다.
		}
		cout << q.front(); // 가장 앞에 남은 k번째 원소를 출력한다.
		
		if (q.size() >= 2) { // 만약, 큐의 크기가 2 이상이라면,
			cout << ", "; // ", "를 붙인다.
		}
		q.pop();	// k번째 원소를 삭제한다!
	}
	cout << ">";
}

---

결과

 

 

11866번: 요세푸스 문제 0