운동하는 개발자/알고리즘, 코딩테스트
Beakjoon] 제곱 ㄴㄴ 수 (백준 1016 코테) - 정수론 (C++)
우용현
2023. 12. 21. 22:31
728x90
🅰️문제주소 : https://www.acmicpc.net/problem/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을 해주는 문제점 때문에 배열의 인덱스값을 실제 값과 동일하다고 볼 수 없다 -> 그러므로 시작점을 구하는 작업을 추가로 해주어야 한다.
728x90