티스토리 뷰

728x90

www.acmicpc.net/problem/1158

 

1158번: 요세푸스 문제

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

www.acmicpc.net

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;
}
728x90
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/02   »
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29
글 보관함