백준 BOJ 1016 - 제곱 ㄴㄴ 수

https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

시간초과가 나서 되게 고민했던 문제.

 

#include <stdio.h>
#include <math.h>
#define ll long long int

bool chk[1000001] = {0};

int main(){
	ll min,max;
	ll sum = 0;
	scanf("%lld %lld", &min, &max);
	sum = max - min + 1;
	for(ll i=2; i*i<=max; i++){
		for(ll j=min/(i*i); i*i*j<=max; j++){
			if(min <= i*i*j){
				if(chk[i*i*j-min] == 0){
					chk[i*i*j-min] = 1;
					sum--;
				}
			}
		}
	}
	printf("%lld", sum);
	return 0;
}

1차로 고민했던 부분은 수의 범위가 너무 넓다는거다

그냥 O(n^2) 알고리즘으로 짜면 시간제한을 훌쩍 넘겨버린다.

그래서 백만번씩 돌면서 다 확인하려는 생각을 접고

min ~ max사이의 수 중 조건에 해당하는 만큼을 빼서 구하자 생각을 했다.

그래서 sum 변수를 만들어서 범위내에 해당하는 수의 개수를 구해줬고,

제곱수의 배수가 아닌 수들이 [제곱 ㄴㄴ 수] 이니까

먼저 제곱수를 구해주기 위해 첫번째 포문을 작성해주었다.

​

두번째 포문에서 2차로 고민하게 됬다.

for(ll j=min/(i*i)) i*i*j<=max; j++)

종료조건은 배수범위가 max를 넘어가면 종료시키니 그렇게 어렵지 않았지만,

j를 1부터 시작하니 시간초과가 일어나서 따로 최소범위를 지정해주어야 했다.

min ~ max 사이의 제곱 ㄴㄴ 수의 최소값을 k라 하자면,

min <= i*i*k 이므로

잘 이항해서 정리해줬다.

ceil 함수는 올림 함수인데, math.h를 포함해야지만이 사용 가능하다.

알아두면 좋을 것 같다.

​

if(min <= i*i*j){

바로 아랫줄에 얘가 있는 이유는 <=이기 때문에 살짝 불안해서 확인차 넣어줬다.

​

3번째로 고민했던 부분은 배수를 제거할때

2*2*4와

4*4같이 겹치는 부분이 생긴다는 점이었다.

배열을 만들어 확인하면 되겠지만, 배열을 만들기엔 너무 큰 범위이다.

문제에서 힌트를 얻었는데,

max의 값이 min + 1000000 이하라는 점이다.

즉 아무리 많아도 제곱 ㄴㄴ수들은 1000000개를

넘을 수 없으므로 1000001개의 배열을 만들어주었고,

min을 뺀 값을 인덱스로 사용했다.

그리고 sum에서 값을 하나씩 빼주는 방법으로 1차로 고민했던 방법을 구현해낼 수 있었다.

​

​

​