[백준 1158] 알고리즘 92일차 : 요세푸스 문제

www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

C++ 큐

이번주 후반부는 쉬어갑시다

 

접근 방법

K번째 사람을 큐에 순서대로 넣고 마지막에 큐에서 빼면서 출력했다.

아직 큐에 넣지 않은 사람(방문하지 않은 인덱스)이 나올때마다 cnt++을 해주고

cnt가 k가 되면 그 사람을 큐에 넣고 cnt를 0으로 초기화했다

인덱스가 n의 범위를 넘어가면 안되므로 i = (i+1)%n으로 해줬다.

 

오답노트

i를 증가시키는 코드를 if문 안에 넣어놔서 무한루프가 돌았었다.

 

소스코드

#include <iostream>
#include <queue>
using namespace std;
bool visit[5000];
int main(){
    int n,k;
    cin >> n >> k;
    queue<int> q;
    int cnt = 0;
    int i = 0;
    while(q.size()!=n){
        if(!visit[i]){
            if(++cnt == k){
                q.push(i+1);
                visit[i] = true;
                cnt = 0;
            }
        }
        i = (i+1)%n;
    }
    cout << "<";
    while(q.size() != 1){
        cout << q.front() << ", ";
        q.pop();
    }
    cout << q.front() << ">";
    return 0;
}