[C++] 2960 에라토스테네스의 체

문제

2960 에라토스테네스의 체

정답

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, k;
    vector<bool> v;    
    cin >> n >> k;
    v.assign(n+1, true);
    int count = 0;
    int answer = 0;
    
    for(int i=2; i<=n; i++){
        if(!v[i]){  //false라면
            continue;
        }
        //else
        //erase
        for(int j=i; j<=n; j+=i){
            if(!v[j])    //false
                continue;
            //else
           v[j] = false;
           count++;
           if(count == k){
               cout << j;
               return 0;
           }
            
        }
        
    }
    return 0;
}

• 핵심은 for(int j=i; j<=n; j+=i) 요 부분이다.

생각의 흐름

알고리즘을 충실히 따르자.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

vector<boo> v;를 이용해서.
7, 3이 주어지면 일단 v.assign(8, true);
그리고 v[2] = false로 시작해서 p의 배수를 false로 바꾼다.
계속 그렇게 진행함. true이면서 p의 배수인 것을 false.
이때 바꿀 때마다 count++ , count == 3이면 stop하고 해당 i를 출력한다.

첫번째 시도 -> 틀렸습니다.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, k;
    vector<bool> v;    
    cin >> n >> k;
    v.assign(n+1, true);
    int count = 0;
    int answer = 0;
    
    while(count != k){
        //find P
        int p;
        for(int i=2; i<=v.size(); i++){
            if(v[i]){
                p = i;
                break;
            }    
        }
        //erase
        for(int i=1; i<=v.size(); i++){
            if(v[i*p]){
               v[i*p] = false;
               count++;
               if(count == k){
                   cout << i*p;
                   return 0;
               }
            }  
        }
    }
    
    return 0;
}

...? 뭐꼬.. 전혀 틀린 점을 못 짚어내겠다.
그래도 생각을 해보자. 내 조건들은 다 '해당하면' 인데, 이전 문제들에서 '해당하지 않으면'으로 설정하는 게 더 예외 없이 처리 될 확률이 높았으니까.

두 번째 시도 -> 틀렸습니다.

int main()
{
    int n, k;
    vector<bool> v;    
    cin >> n >> k;
    v.assign(n+1, true);
    int count = 0;
    int answer = 0;
    
    while(count != k){
        //find P
        int p;
        for(int i=2; i<=n; i++){
            if(!v[i]){  //false라면
                continue;
            }
            //else
            p = i;
            break;
        }
        //erase
        for(int i=1; i<=n; i++){
            if(!v[i*p])    //false
                continue;
            //else
            {
               v[i*p] = false;
               count++;
               if(count == k){
                   cout << i*p;
                   return 0;
               }
            }  
        }
    }
    
    return 0;
}

while(count != k) 여기서 문제가 생겼을 것 같다. 사실 밑에서 if문으로 count == k 검사를 하고 있기 때문에 조건의 의미가 없다고 생각하긴 했었다.

세 번째 시도 -> 해결!

for(int j=i; j<=n; j+=i){
            if(!v[j])    //false
                continue;
            //else
           v[j] = false;
           count++;
           if(count == k){
               cout << j;
               return 0;
           }
            
        }

ㅋㅋㅋㅋㅋㅋwhile을 바꿔도 해결 X
요 부분이 핵심이었다. 기존의 내 방식은 for(int i=1; i<=n; i++)이 부분에서 v의 선언 범위를 넘어갈 수도 있었다. 즉, p * i <= n 을 대비하지 못한 코드였다는 소리.
n 까지만 검사하면 되니까 이 부분을 잘 고려했어야 함!

참고

참고한 건 없었다. 그냥.. 정답 한 번 봄ㅎ;