boj 11866 요세푸스 문제 0 c++

boj 11866 요세푸스 문제 0 c++

 

 

쉽게 말해 (원형) 큐 문제이다.

1 번째 요소를 시작점으로 하여 원을 그리면서 N개의 요소를 도는 동안

k 번째 요소를 제거하고, 다시 그 원에서 k + 1번째 요소부터 시작하여 다시 k번째가 되는 녀석을 제거하는 것을

반복한다.

 

필자 코드의 기본적인 논리는 아래와 같다.

 

1. N, K를 받음.

2. 1~N 을 queue에 담고.

3. while (true)인 동안

   for i = 1 ~ k(즉, k번 반복 하면서)

   ​ 만약 i가 k가 아니라면.
   ​ queue의 맨 첫 요소를 빼고 다시 넣는다.

   ​ 만약 i가 k라면.

   ​ queue의 맨 첫 요소를 빼고 출력한다.

 

#include <bits/stdc++.h>
using namespace std;
/*
1. N, K를 받음.

2. 1~N 을 queue에 담고.

3. while (true)인 동안

   for i = 1 ~ k(즉, k번 반복 하면서)

    만약 i가 k가 아니라면.
           queue의 맨 첫 요소를 빼고 다시 넣는다.

    만약 i가 k라면.  

          queue의 맨 첫 요소를 빼고 출력한다.
*/

int N, K; // 1~ 1000범위.
queue<int> Q;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K;

    cout << '<';
    for (int i = 1; i <= N; i++)
    {
        Q.push(i);
    }
    while (true)
    {
        if (Q.empty())
            break;
        for (int i = 1; i <= K; i++)
        {
            if (i != K)
            {
                int t = Q.front();
                Q.pop();
                Q.push(t);
            }
            else
            {
                cout << Q.front();
                Q.pop();
                if (!Q.empty())
                    cout << ", ";
            }
        }
    }
    cout << '>';
    return (0);
}

 

 

백준 11866 요세푸스 문제 0 cpp