[백준] 1158.cpp : 요세푸스 문제

www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

---

• 원을 이루면서 앉아 있다는 것은, 앞에서 순서가 지나가면 그 사람이 뒤로 가는 것과 같다.
• ex) A B C D --> B C D A
• 모든 사람들을 큐에 넣고 사람들을 매 반복마다 뒤로 보내는데, K번째 사람일 경우에는 출력하면서 제거해주면 된다.

---

#include <iostream>
#include <queue>

using namespace std;

int n, k;

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

    for(int i = 1 ; i <= n ; i++)
    {
        q.push(i);
    }
    cout << "<";
    while(q.size() > 1)
    {
        for(int i = 0 ; i < k - 1 ; i++)        // 앞에서부터 K - 1 명의 사람들을 뒤로 보낸다
        {
            q.push(q.front());
            q.pop();
        }
        cout << q.front() << ", ";              // 그러면 순서대로 제거해야 되는 K 번째 사람이 앞에 남기 때문에
        q.pop();                                // 출력하고 제거
    }
    cout << q.front() << ">" << endl;
}

---

• 2등 소스코드 참고 : www.acmicpc.net/source/16851639
• 한번 반복할때마다 제거 대상 뒤에 있는 배열을 전부 재조정해주었다.

---

#include <cstdio>

using namespace std;

int main()
{
    int d[5001];
    int n, k;
    int now = 0;
    scanf("%d %d", &n, &k);
    for(int i = 1 ; i <= n ; i++) d[i] = i;
    printf("<");

    while(n > 1)
    {
        now = (now + k) % n;
        if(now == 0) now = n;
        
        printf("%d, ", d[now]);
        for(int i = now ; i < n ; i++) d[i] = d[i+1];
        now--;
        n--;
    }
    printf("%d>\n", d[1]);
}