백준 1158-조세푸스 문제

문제 바로가기

티어

🥈실버 4

문제 풀이 방식

우선 종만북을 본 사람이라면 알 수 있듯 큐나 연결리스트를 사용한 구현이 모두 가능한 문제이다.
위 문제에서 나온 예시를 분석해보면

첫번째 입력 상태: 1,2,3,4,5,6,7
두번째 상태: 2,3,4,5,6,7,1
세번째 상태: 3번째 사람을 제거해야한다.
따라서 4,5,6,7,1,2가 되고 3이 요세푸스 수열의 첫번째 값으로 들어간다.

힌트

큐의 특징을 잘 생각해보자.
큐는 선입선출의 구조를 가지고있고, 우리가 출력해야하는 값 역시 선입선출이다.

정답 코드

#include<iostream>
#include<queue>
using namespace std;
#define MAX  5005
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, k;
	cin >> n >> k;
	queue<int>q;
	for (int i = 1; i <= n; i++) {
		q.push(i);
	}
	cout << "<";
	while (q.size() > 1) {
		for (int i = 1; i < k; i++) {
			int temp = q.front();
			q.pop();
			q.push(temp);//큐는 한방향으로만 작동하기 때문에 맨 뒤에 넣으려면 이렇게 해야
		}
		cout << q.front() << ", ";
		q.pop();
	}
	cout << q.front() << ">" << "\n";
}