알고리즘 문제풀이
[백준 1158] 알고리즘 92일차 : 요세푸스 문제
SiO2whocode
2021. 2. 25. 12:51
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