[백준알고리즘] 1016번: 제곱 ㄴㄴ 수 -C++

[백준알고리즘] 1016번: 제곱 ㄴㄴ 수 -C++

1016번: 제곱 ㄴㄴ 수 (acmicpc.net)

1016번: 제곱 ㄴㄴ 수

시간 복잡도 때문에 문제 푸는데 좀 골머리를 앓았다 ㅎㅎ;

 

문제를 푸는 데 있어서 시간 복잡도를 생각할 부분이 두 개 있었다고 생각한다.

 

실제 제출해서 통과한 시간은 다른 분들이 10ms 안팎인 것에 비해 144ms라는 결과가 나왔지만, 푸는 과정은 거의 비슷했지만, 다른 분들은 다 배열을 썼기 때문에 이것은 STL을 사용했기 때문에 발생한 추가적인 시간이라고 생각한다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

문제를 푸는 과정은 두 단계로 분류할 수 있다.

1. 소수를 확인하고, 소수의 제곱을 구한다.
2. 소수의 제곱의 배수인 값 중 \([min, max]\)의 범위의 값을 제외

 

소수를 구하는 이유는 문제의 요구조건 때문이다. 제곱수로 나누어 떨어지지 않는 수의 개수를 구해야 하는데, 모든 수는 소수의 곱으로 나타낼 수 있기 때문에 모든 수의 제곱수는 소수의 제곱수의 배수로 표현할 수 있다.

 

즉, 자연수는 합성수와 소수로 나눠서 생각할 수 있는데, 합성수는 소수의 곱으로 표현할 수 있기 때문이다. 아래의 위키를 살펴보자.

합성수 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

합성수 - 위키백과, 우리 모두의 백과사전

 

그리고 위의 두 단계가 시간 복잡도를 고려해야할 부분이다. 차례대로 살펴보도록 하겠다.

 

---

 

소수 찾기 (소수의 제곱 찾기)

기본적으로 에라토스테네스의 체를 사용해서 소수를 찾기 시도했다.

 

다만, 소수를 찾는 범위를 무턱대고 \(max\)로 잡아주면 안 된다.

 

사실 문제에서 요구되는 것은 '제곱수로 나누어 떨어지지 않는 수'이기 때문에, \(max\)의 제곱근까지만 소수를 찾아주면 된다.

따라서 <cmath> 헤더의 sqrt를 사용해 제곱근까지 소수를 찾아주었고, 소수인 값을 찾으면 해당 소수의 제곱수를 기록했다.

 

소수의 제곱의 배수 찾기

다시 문제의 요구 조건이 '제곱수로 나누어 떨어지지 않는 수'이라는 것을 상기해야 한다.

따라서 위의 과정에서 찾은 소수의 제곱들에 대해 이제는 배수를 찾아주어야 한다.

 

여기서도 사실 각 소수마다 1배, 2배, 3배... 과정을 거쳤더니 시간 초과가 발생했었는데, 이를 고쳤더니 통과했다.

 

각 소수마다 1배부터 차례대로 확인할 필요가 없다는 것을 눈치채고 난 뒤였다.

 

예를 들어서 \(min\)이 \(1,000,000\) 라면, 소수의 제곱인 첫 번째 값인 \(4\) 는 1배부터 차례대로 확인한다면, \(250,000\) 번 쓸모없는 확인을 해야 한다.

 

따라서 각 소수 \(p\)에 대해서 \(min / p\) 배부터 차례대로 비교해주었다.

\(min\)이 \(p\)에 대해서 나누어 떨어지냐에 따라서 시작하는 정수배의 값이 다르기 때문에 조건을 추가해준 것은 아래의 코드를 보면 확인할 수 있다.

 

---

 

아래는 위의 방식으로 푼 C++ 코드다. 다른 분들과 다르게 STL의 vector, set을 사용했기 때문에 시간이 추가적으로 더 요구되었다.

#include <iostream>
#include <vector>
#include <set>
#include <cmath>

void solve(void);

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

	solve();
}

void fill_prime_square(uint64_t max, std::vector<uint64_t>& prime_square)
{
	uint64_t field_size = sqrt(max) + 1;				// 시간복잡도!
	bool* erathosthenes = new bool[field_size];
	std::fill_n(erathosthenes, field_size, true);
	
	erathosthenes[0] = false;
	erathosthenes[1] = false;
	for (uint64_t i = 2; i < field_size; i++)
	{
		if (!erathosthenes[i])
			continue;

		prime_square.push_back(i * i);

		uint64_t mul = 2;
		while (i * mul < field_size)
		{
			erathosthenes[i * mul] = false;
			mul++;
		}
	}
}

void solve(void)
{
	uint64_t min, max;
	std::cin >> min >> max;

	std::vector<uint64_t> prime_square;
	fill_prime_square(max, prime_square);

	std::set<uint64_t> answer;
	for (uint64_t i = 0; i < prime_square.size(); i++)
	{
		uint64_t t = prime_square[i];

		uint64_t mul = min / t + (min % t ? 1 : 0);		// 시간복잡도!
		while (t * mul <= max)
		{
			answer.insert(t * mul);
			mul++;
		}
	}

	std::cout << max - min + 1 - answer.size();
}