몇개의 로직을 생각하는데에 조금의 어려움이 있었지만 골드1의 난이도 치고는,,? 꽤나 쉽게 풀 수 있던 문제였다. 이 문제를 풀면서 확실히 수학관련 지식이 많이 부족하다는 생각을 했다,,,,,,, 수학 열심히 공부해야지
이 문제는 min부터 max까지 제곱수로 나누어 떨어지지 않는 수를 세는 문제이다. 여기서 제곱수는 정수의 제곱을 뜻한다.
예를 들어 1부터 10까지의 제곱 ㄴㄴ 수는
1
2
3
4 - 2의 제곱수로 나누어 떨어짐
5
6
7
8 - 2의 제곱수로 나누어 떨어짐
9 - 3의 제곱수로 나누어 떨어짐
10
1, 2, 3, 5, 6, 7, 10
이다.
처음에는 1부터 max까지의 수를 모두 배열에 담고 그 중 제곱 수를 쭉 지워주는 로직을 만들었다.
하지만 max의 최대값이 1,000,001,000,000으로 이 크기의 배열을 만들고 계산하는 것이 굉장히 부담되었다,, 잘 생각해보니 굳이 1에서 max까지 다 판별하지 않아도 된다는 것을 알게되었다.
어쩌피 찾아야 할 값은 min과 max사이의 값이니 min에서 max까지의 값만 배열에 넣어줘도 상관없었다.
그러기 위해서 필요한 것들은 다음과 같았다.
1. min에서 max까지의 수를 담는 배열
( max의 최대 입력 값은 min + 1,000,000이므로 1,000,000크기의 배열이 필요함)
2. min보다는 큰 제곱수로 나누어떨어지는 최소 값
- 어쩌피 min 아래 값들은 체크할 필요 없다.
여기서 제일 중요한 값은 2번 값
으로 실제로 이 값을 빠르게 찾아오는 로직에 대해서 많은 고민을 하였다,,,
min과 max 사이에 있는 제곱수를 모두 삭제하기 위해서는 sqrt(max)까지 for문을 돌면서 제곱수를 찾아야 하는데 그 이유는 sqrt(max)값을 넘어가는 수의 제곱수는 무조건 max의 값을 넘어가기에 비교할 필요가 없기 때문이다.
이제 min보다 큰 제곱수로 나누어떨어지는 최소 값에서 max 값까지 for문을 돌며 제곱수를 삭제하여 주고 제곱수가 아닌 수를 카운트해주기만 하면 된다.
min보다 큰 제곱수로 나누어 떨어지는 최소 값
에서 max값 까지 제곱수로 나누어떨어지는 수 찾기#include<iostream>
#include<cmath>
using namespace std;
int main(){
long long min, max, powNum, j;
long long array[1000001] = {};
int count = 0;
cin >> min >> max;
for(long long i = 2; i <= sqrt(max); i++){
powNum = i * i;
j = (min + powNum - 1) / powNum * powNum;
for( ; j <= max; j += powNum){
array[j - min] = 1;
}
}
for(long long i = min; i <= max; i++){
if(array[i - min] == 0){
++count;
}
}
cout << count;
}