Beakjoon] 제곱 ㄴㄴ 수 (백준 1016 코테) - 정수론 (C++)

---

🅰️문제주소 : https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

 

🚩문제 

 

 

🪡풀이 

 - 에라토스테네스의 체를 응용해야 한다. 제곱수로 나누어 떨어지지 않는 수를 찾아야 하므로 반대로 제곱수를 계속 곱해가며 지워나가야 한다.
 - 값이 무엇인지가 중요한 게 아니라 개수만 체크하면 되기에 bool타입의 배열을 사용한다.
 - min과 max의 값이 엄청 크므로 overflow에 주의해야 한다.
 - 추가로 메모리 사용에도 주의해야 한다

 

 

☕코드는 아래 숨김

//no 40
#include <iostream>
#include <vector>
#include <math.h>

int main() {

	std::ios::sync_with_stdio(false);
	std::cout.tie(0);
	std::cin.tie(0);

	unsigned long long min, max;

	std::cin >> min >> max;

	std::vector<bool> check(max - min + 1, false);

	for (unsigned long long i = 2; i <= std::sqrt(max); ++i) { //2의 제곱수 부터 체크하기 시작
		unsigned long long pow = i * i;
		unsigned long long start = min / pow; //몇배수 부터 체크해야하는지 시작점을 잡기 위함
		//만약 MIN값이 6이면 시작점은 8이 될것이다(7은 제곱수가 아니므로) 그러기 위해서는 나머지가 있을때 
        //1을 더해주어야 한다 단순 몫으로 구하면 시작값 6보다 작은 4부터(4*1) 찾게된다
		if (min % pow != 0) 
			start++;

		for (unsigned long long j = start; pow * j <= max; ++j) {
			check[(pow * j) - min] = true;
		}
	}
	
	unsigned long long result = 0;

	for (unsigned long long i = 0; i < check.size(); ++i) {
		if (!check[i])
			result++;
	}

	std::cout << result;

	return 0;
}

 

💡느낀점 

 - 에라토스테네스의 체 응용방법
 - 기존 문제처럼 max값만큼 배열선언 시 메모리 초과 오류가 발생한다. 배열의 크기를 최소화할 수 있게    max-min을 해주어야 한다
 - max-min을 해주는 문제점 때문에 배열의 인덱스값을 실제 값과 동일하다고 볼 수 없다 -> 그러므로 시작점을 구하는 작업을 추가로 해주어야 한다.

---