[백준 #1158] 요세푸스 문제 (C++)

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

문제에서는 n이 7, k가 3이기 때문에

1부터 7까지 큐에 넣어주고

<1, 2, 3, 4, 5, 6, 7>

큐 사이즈가 1보다 클 때 까지 for문을 돌며 

0, 1 번째 인덱스 원소는 큐에 다시 추가해준 후 앞에서 제거하고

2번째 인덱스 (즉 k번째 사람)은 출력 후 제거해주었다.

 

그리고 큐 안에 원소가 하나만 남았을 때 while문을 나와 해당 요소를 출력 후 제거해주었다.

출력 형식이 < , , , > 여서

마지막 출력 값에는 ',' 을 붙이지 않기 위해 한 것이다.

 

1

2

3

4

5

6

7

3

4

5

6

7

1

2

4

5

6

7

1

2

6

7

1

2

4

5

7

1

2

4

5

2

4

5

7

1

4

5

7

1

7

1

4

5

1

4

5

5

1

4

1

4

1

4

4

 

#include <iostream>
#include <queue>
using namespace std;

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

    int n, k;
    queue<int> q;
    cin >> n >> k;
    int idx = k-1;

    for (int i=1; i<=n; i++) {
        q.push(i);
    }

    cout << '<';

    while (q.size() > 1) {
        for (int i=0; i<idx; i++) {
            q.push(q.front());
            q.pop();
        }
        cout << q.front() << ", ";
        q.pop();
    }
    cout << q.front() << '>';
    q.pop();

    return 0;
}