백준 1158 오세푸스 문제 c++ [컴공과고씨]

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

1158번: 요세푸스 문제

일단 규칙을 파악해보면 n = 7, k=3 일 때

12[3]45[6]7

12[4]57

[1]25[7]

이런식으로 []안에 있는 것을 출력할 것이다.

쉽게 생각해보면 자기 차례가 아닌 것을 뒤로 보내주면 연결이 된다.

12[3]45[6]712[4] 이런식으로 말이다.

바로 queue를 쓰면 쉽게 이 방식을 구현할 수 있다.

자기 차례가 아니면 뒤로 옮겨주고 자기 차례인 경우 pop을 해주면 된다.

 

ps. 출력 형식이 <> 안에 있으니 주의 하도록 하자.

 

단계별 풀이

1. 정답을 저장할 vector와 사이클을 돌릴 queue 선언

2. 큐가 empty가 될 때 까지 반복

3. k-1 만큼 수를 뒤로 보냄 (front를 push 후 pop)

4. k번째 일 때 수를 vector에 저장하고 pop

5. 출력

 

전체코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
    int n, k;
    vector<int> v;
    queue<int> q;
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        q.push(i);
    }
    while(!q.empty()){
        for (int i = 0; i < k-1; i++){
            q.push(q.front()); // 자기 차례가 아닌 경우 수를 뒤로 보냄
            q.pop();
        }
        v.push_back(q.front());//차례 도달 시
        q.pop();
    }
    cout << "<";
    for (int i = 0; i < n-1;i++){
        cout << v[i] << ", ";
    }
    cout << v[n - 1] << ">";
    return 0;
}

체감난이도	걸린시간	참고	후기	사용 문법
하	28min	x	출력 형식 지키지 않아 조금 오래걸렸음....	queue