[#66][알고리즘] 조세퍼스 문제0
백준 > 조세퍼스 문제0
문제 링크(https://www.acmicpc.net/problem/11866)문제
조세퍼스 문제는 다음과 같다.
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 ≤ 1,000)
출력
예제와 같이 조세퍼스 순열을 출력한다.
예제 입력
7 3
예제 출력
<3, 6, 2, 7, 5, 1, 4>
C++풀이
#include <iostream>
#include <queue>
using namespace std;
int main() {
int a,b;
queue<int> que;
cin >> a >> b;
cin.ignore();
for (int i = 1; i <= a; i++) {
//1번부터 a번까지 큐에 push
que.push(i);
}
int index = 0;
cout << "<";
while (!que.empty()) {
//큐에 원소가 있을 동안
index++;
if (index%b != 0) {
//index가 b의 배수가 아닐 때. (b번째 원소가 아닐 때)
int a = que.front();
que.pop();
que.push(a);
//그 원소를 pop후, 맨 뒤로 push
}
else {
//index가 b의 배수일 때. (b번째 원소일 때)
int a = que.front();
que.pop();
//그 원소를 pop
if (que.size() == 0) {
//출력 폼 맞추기 위해서
cout << a;
}
else {
cout << a << ", ";
}
}
}
cout << ">" << endl;
return 0;
}
| cs |
댓글
댓글 쓰기