백준 1016번 제곱 ㄴㄴ 수

문제 링크입니다: https://www.acmicpc.net/problem/1016

처음에는 vector를 이용하여 풀었는데 중복된 제곱수를 추가하는 바람에 틀렸습니다.

그래서 algorithm 헤더 파일을 추가하여 find 함수를 이용하여 중복된 제곱수를 방지했더니 시간 초과가 발생했습니다.

따라서 언제나처럼 배열을 이용하여 풀었는데 한가지 유의사항은 인덱스를 0부터 시작하기 위해 

arr[quotient*square - minNum]에 제곱수임을 표시해야한다는 점입니다.

#include <iostream>

//#include <vector>

//#include <algorithm>

using namespace std;

 

const int MAXSQRT = 1000000 + 1;

 

long long minNum, maxNum;

long long arr[MAXSQRT];

 

//미리 제곱수를 계산

void preCalculate(void)

{

        for (long long i = 2; i * i <= maxNum; i++)

        {

                 long long square = i * i;

 

                 long long quotient = minNum / square;

                 //minNum이 제곱수에 나뉘어지지 않는 다면

                 if (minNum % square != 0)

                         quotient++;

 

                 while (quotient * square <= maxNum)

                 {

                         //vector 사용할 경우 find 때문에 시간 초과 발생

                         //이미 추가한 제곱수는 추가하지 않는다

                         //if (find(v.begin(), v.end(), quotient*square) == v.end())

                                 //v.push_back(quotient * square);

                         arr[quotient*square - minNum]++; //arr index 0부터 채우기 위해

                         quotient++;

                 }

        }

}

 

long long numOfNotSquare(void)

{

        long long cnt = maxNum - minNum + 1;

       

        for (int i = 0; i < maxNum - minNum + 1; i++)

                 if (arr[i]) //제곱수라면

                         cnt--;

        return cnt;

}

 

int main(void)

{

        cin >> minNum >> maxNum;

 

        preCalculate();

 

        cout << numOfNotSquare() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~