[백준1016] 제곱ㄴㄴ수 (C++)

📌 문제

BOJ 바로가기

min과 max 사이 제곱수로 나누어떨어지지 않는 수의 개수를 구하는 문제이다.

🗡 풀이

📍 N을 설정하는 것이 중요하다.

📍 예를 들어 min = 30, max = 45 라고 가정하자. 2 * 2 * 1 부터 시작해서 max 범위를 초과하지 않는 수를 지워주면 답을 구할 수 있을 것 같다.

📍 하지만 이렇게 구하면 시간초과가 뜬다. min은 최대 1조까지 될 수 있기 때문... 이 경우 쓸데없는 반복이 굉장히 많아진다.

📍 따라서 2 * 2 * 1 부터 탐색하는 것이 아니라, 2 * 2 * N 부터 탐색해주어야 한다. 이때 2 * 2 * N 은 min보다 큰 가장 작은 제곱ㄴㄴ수가 아닌 수이다. 따라서 N을 구하면 이 문제는 끝난다.

📍 N = min / (i * i);
아까의 예를 다시 가져와서, min = 30, max = 45 라고 다시 가정하면 N = 30 / (2 * 2) = 7 이다. 하지만 7 * 2 * 2 = 28이므로 min보다 작다. 그래서 N을 1 올려준 후 제곱ㄴㄴ수가 아닌 수를 지워 나간다. 이 과정을 계속해서 반복한다.

🥶 처음에는 런타임에러 때문에 애먹고, 런타임에러를 고치니 시간초과 때문에 애먹었다😭 구글링을 통해 문제를 해결했다.

🚩 정답 소스코드

#include <iostream>
#include <math.h>
using namespace std;

long long  num[1000001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	long long min, max;
	cin >> min >> max;
	for (long long i = min; i <= max; i++) {
		num[i - min] = i;
	}
	// 에라토스테네스의 체 (변형)
	for (long long i = 2; i * i <= max; i++) {
		long long N = min / (i * i);
		if (min % (i * i) != 0)
			N++;
		while (N * i * i <= max) {
			num[N * i * i - min] = 0;
			N++;
		}
	}
	// 출력
	int ans = 0;
	for (long long i = min; i <= max; i++) {
		if (num[i - min] != 0)
			ans++;
	}
	cout << ans;
}

🚩 시간초과 소스코드

#include <iostream>
#include <math.h>
using namespace std;

long long  num[1000001] = { 0 };

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	long long min, max;
	cin >> min >> max;
	for (long long i = min; i <= max; i++) {
		num[i - min] = i;
	}
	// 에라토스테네스의 체 (변형)
	for (long long i = 2; i * i <= max; i++) {
		if (i * i >= min && num[i * i - min] == 0) continue;
		for (long long j = 1; i * i * j <= max; j++) {
			if (i * i * j >= min)
				num[i * i * j - min] = 0;
		}
	}
	// 출력
	int ans = 0;
	for (long long i = min; i <= max; i++) {
		if (num[i - min] != 0)
			ans++;
	}
	cout << ans;
}