Search
Duplicate
📗

에라토스테네스의 체

주차
문제번호
2960
언어
C++
티어
실버
유형
수학
구현
정수론
소수 판정
에라토스테네스의 체
nj_Blog
nj_상태
이해도
100%
풀이
사람
이해도 2
13 more properties

문제접근

2부터 n까지 수를 큐에 넣음
조건에 맞는 녀석만 큐에서 빼내고 k번째를 빼낼때까지 동작 반복

놓쳤던 부분

while문을 queue의 size로 돌릴때는 큐의 사이즈가 변동이 있을 경우가 있기 때문에 조심해야함

코드

2020 KB

0 ms

#include <iostream> #include <queue> using namespace std; int main(void) { int n,k; int p; queue<int> q; int answer; ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; for (int i = 2; i <= n; i++) q.push(i); while (k > 0) { p = q.front(); answer = p; q.pop(); k--; int i = 0; int q_size = q.size(); while (k > 0 && q_size > i) { i++; if (q.front() % p == 0) { k--; answer = q.front(); q.pop(); } else { q.push(q.front()); q.pop(); } } } cout << answer; return (0); }
C++
복사