BOJ. 11866

#BOJ11866

요세푸스 문제 0

요세푸스 문제를 풀면서 최근에 티어로 꿀을 좀 많이 빨았다. 이게 요세푸스 문제가 구현은 굉장히 쉬운데 수학적으로 어려워서 책 끄적거리면서 좀 찾다보면 달달하게 풀 수 있다. 하지만 요세푸스 문제의 기본적인 관점은 스택이기 때문에 이에 입각해서 푸는 방법을 제시해보려고 한다. 이 블로그를 볼 대상들이 대부분 학교의 학우들일거 같아서 개인적인 의견을 조금 남기자면 스택에 대해서 기본적인 개념을 알게 된 후에 가장 풀었을 때 도움이 많이 되는 문제들 중 하나였다. 앞으로 내가 다루게 될 클래스 2의 문제들은 대부분 실버 하위권에서 중위권 문제로 자료구조를 이용하는 문제가 많다. 이 쪽 내용들을 다루다 보면 2학기에 우리가 데이터구조 시간에 배운 것들이 이런식으로 문제와 일상에서 활용될 수 있겠구나 생각이 들기 시작할 것이다.
기본적으로 이 요세푸스 문제는 스택에서 pop하는것을 순서대로 출력하여서, 최종적으로 모두 pop한 스택을 출력하는것이 목적이다. 이 문항 같은 경우에는 제한 조건도 빡세지 않고, 메모리 문제도 없으니 그냥 구현하면 된다. 특이 사항으로는 꺽쇠를 처리해주는 부분을 활용하기 위해서 size()를 사용해서 해결했다는 부분이다.

# include "iostream"
# include "queue"

using namespace std;

int main(void){
   int N, K;
   cin >> N >> K;
   queue<int> arr;
   for (int i = 1; i <= N;i ++){
       arr.push(i);
   }

   cout << "<";
   while(arr.size() != 1){
       for (int i = 0; i < K - 1; i++) {
           arr.push(arr.front());
           arr.pop();
       }
       cout << arr.front() << ", ";
       arr.pop();
   }
   cout << arr.front() << ">";

}