[BOJ] 백준 1016번 제곱 ㄴㄴ수 (Java)

#1016 제곱 ㄴㄴ수

난이도 : 골드 1

유형 : 정수론 / 에라토스테네스의 체

1016번: 제곱 ㄴㄴ 수

▸ 문제

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

▸ 입력

첫째 줄에 두 정수 min과 max가 주어진다.

▸ 출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

 

문제 풀이  

최대가 1조(10^12)이다. 그래서 int형으로는 풀 수 없고 범위를 넓게 설정해야 한다. 그런데 제곱수에 나누어 떨어지는 수를 카운트해줘야 하는데 이를 일일히 셀 수는 없는 노릇이다. 특히나 중복을 제거해주면서 탐색을 해줘야 하는데  1조에 해당하는 배열 크기를 할당할 수도 없어서 boolean체크도 할 수 없다.

 

따라서 방법은 좌표압축 하나다. 주어진 범위를 보면 10^12 ~ 10^12 + 10^6이라서 다뤄야 할 수는 최대 10^6임을 알 수 있다. 그러므로 좌표압축을 사용하면 100만 크기의 배열을 할당해서 제곱수로 나눠지는 값들을 체크해줄 수 있다.

 

먼저 min, max 두 수 주어졌을 때 나올 수 있는 최대의 제곱수는 Math.sqrt(max)이다. 이 크기가 탐색 최대 범위이다.

• 만약 max가 최댓값으로 주어졌다면 Math.sqrt(10^12+10^6) = 1000000.499999875 제곱수 최댓값은 10^6이다. 

 

그럼 우리는 2부터 Math.sqrt(max)까지의 제곱수 중 나누어 떨어지는 수들만 제거해주면 된다. 이는 에라토스테네스의 체 소수 분별 방식을 차용해주면 된다. 이제 제곱수를 제거하는 로직만 구상해주면 된다.

for(long i=2; i*i<=e; i++) {
  // 제곱수 제거하는 로직
  // ...
  
}

 

만약 min = 10, max = 100이라고 하자. 그럼 탐색해야 할 제곱수는 i: 2~10이고 그에 나누어 떨어지는 수를 제거해주면 된다. 제곱수는 (제곱수/min 의 몫) * 제곱수로 구할 수 있다 (단, 나머지가 0이 아닐 경우 +1을 해줘야 한다). 이유는 다음과 같다.

• min값인 10를 제곱수 pow = i*i = 2*2 = 4로 몫(tmp)을 구하면 min/pow = 10/4 = 2이다.
• 나머지가 0이 아니므로 +1을 해주면 값은 tmp=3이다.
  • 나머지 0이 아닐 경우 +1을 해주는 이유는 min*(i*i)보다 같거나 큰 제곱수로 나눠지는 값을 구하기 위함이다.
  • tmp(= 3) >= min/i*i으로, tmp는 (최솟값/제곱수)보다 크거나 같은 값이다.
• 구한 값(tmp)에 다시 pow를 곱한다.  3*(2*2) = 12이다.
  • 이 수가 최솟값(10)을 시작으로 제곱수(i*I)를 나눌 수 있는 가장 작은 값이 되는것이다.
  • 실제로 [10, 100]에서 처음으로 제곱수로 나누어지는 값 12이다.
• 이젠 tmp의 크기를 1씩 늘려가면서 최댓값까지 탐색하여  제곱수로 나눠지는 가능한 모든 값들을 체크해준다. 4*4, 5*4, 6*4 ... 

이 방식을 제곱수 i: 2 ~ Math.sqrt(100) = 10까지 반복해주면 된다.

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long s = Long.parseLong(st.nextToken());
		long e = Long.parseLong(st.nextToken());
		
		long count = e-s+1;
		boolean[] check = new boolean[(int)count];
		
		for(long i=2; i*i<=e; i++) {
			long pow = i*i; // 제곱수 
			long tmp = s/pow;  // 제곱수로 나눠지나? 
			if(s%pow != 0) { // 제곱수 아니면 +1 
				tmp += 1;
			}
			
			for(long j = tmp; j*pow<=e; j++) {
				int canSqrt = (int)(j*pow-s);
				if(!check[canSqrt]) {
					check[canSqrt] = true; // 나누어 떨어지는 수 범위 초과로 -s 해서 저장
					count--;
				}
			}
		}
		System.out.println(count);
	}
}