[BOJ/백준] 1016번 : 제곱 ㄴㄴ 수 (C++)

[BOJ/백준] 1016번 : 제곱 ㄴㄴ 수

BOJ 1016

문제 해석

• min값만 보면 수가 1000000000000로 엄청 커보인다. 하지만 실제로는 min과 max 사이의 수들 안에서 구하는 것이므로 1000000 데이터만 확인하면된다.
• 에라토스테네스의 체 알고리즘 방식을 응용하여 제곱수를 판별해내면 되곘다는 생각이 들었다.

풀이

• 첫번째, 주어진 범위 [Min, Max]에서 제곱수 배수에 해당하는 숫자들을 제거할 것이다. pow = i * i일 때, 제거하려는 숫자는 pow * k 형태의 숫자들이다. 따라서 Min <= pow * k <= Max를 만족하는 경우를 찾아 제거해야한다.

• 모든 k에 대해 pow * k를 계산하고 범위에 포함되는지 확인할 수 있으나, 비효율적이다.

• Min 이상에서 시작하는 첫 번째 배수를 찾으면 효율적으로 탐색을 시작할 수 있다고 생각이 들었다.

• pow * k >= Min이 성립해야 하므로 k는 최소한 Min/pow 이상이여야 한다. 여기서 Min/pow가 정수가 아닌 경우가 있기 때문에, 나머지가 0이 아니라면 k를 1증가시키도록 한다.

• 이렇게 시작 index를 설정하여 범위 외의 배수를 계산할 필요가 없어졌다.

코드

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

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long Min, Max;
    cin>>Min>>Max;//최소값, 최대값 입력

    vector<bool> Check(Max-Min+1);

    for(long i=2; i*i<=Max; i++){
        long pow=i*i;//제곱수
        long start_index = Min/pow;//최소값/제곱수 단, 나머지가 0이 아니면 1을 더한다

        if(Min%pow != 0) start_index++;//나머지 0이 아니면 1을 더함

        for(long j = start_index; pow*j <= Max; j++){//pow*j가 Max를 넘으면 알고리즘 종료
            Check[(int)((j*pow)-Min)]=true;
        }
    }

    int cnt=0;

    for(int i=0; i<=Max-Min; i++){
        if(!Check[i]) cnt++;//개수 확인
    }

    cout<<cnt<<"\n";
}