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

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

1158번: 요세푸스 문제

 

 

문제 이해

이 문제를 이해하기 위해서 종이에 그림을 그려 보라.

단번에 어떤 자료구조가 필요할지 떠오르지 않아도 괜찮다.

 

앞에서 K번째 원소까지 탐색하고, 원소를 지우고,

탐색하고, 지우고... 를 반복하면 되겠구나!

하고 떠오르면 문제 이해가 끝났다.

 

 

 

Queue

이제 큐를 사용해보자

K번째 원소까지 어떻게 셀까?

 

1. 큐의 맨 앞 원소를 뒤에 붙이고(push), 그 원소를 지운다(pop)

이 과정을 K번동안 반복한다.

 

그럼 초기에 앞에서 K번째에 있던 원소가 맨 앞으로 왔을 것이다.

 

2. 이제 그 원소를 출력하고, pop한다.

 

1. 과 2. 의 과정을 N번 반복하면 queue에 모든 원소가 지워진 채로 있을 것이다.

 

 

---

SMALL

코드

 

//
//  main.cpp
//  boj
//
//  Created by LeeYeEun on 2021/07/06.
//

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    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 = 0; i < k - 1; i++) {
            q.push(q.front());
            q.pop();
        }
        cout << q.front() << ", ";
        q.pop();
    }
    cout << q.front() << ">";
    return 0;
}

 

 

구현에 유의해야 한다.

마지막 원소 뒤에는 ', '가 없고 '>'만 출력된다.