[백준] 1016 제곱ㄴㄴ수 - Java

 

 

 

얼핏 보기에는 쉬워 보이는 문제이다.

1부터 자기 자신까지 전부 다 나눠보는 방식으로도 접근할 수 있긴 하지만..

문제 조건에서 주어지는 수의 범위가 너무 크기 때문에 위의 방법대로 접근하면 시간초과 문제가 발생한다.

 

어떤 수의 제곱에 관련된 수가 있었는데... 

소수를 찾을 때 사용했던 에라토스테네스의 체 알고리즘에서 제곱수를 다룬 적이 있었다.

이 알고리즘으로 접근해보자.

 

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		long min = sc.nextLong();
		long max = sc.nextLong();
		
		boolean[] check = new boolean[2000000];
		long finish = (long)Math.sqrt(max);
		
		
		for(long i = 2; i<finish+1; i++) {
			long temp = i*i;
			long start = 0;
			if(min % temp == 0 ) {
				start = min / temp;
			}else {
				start = (min / temp) + 1;
			}
			for(long j = start; j*temp<max+1; j++) {
				check[(int)((j*temp)-min)] = true;
			}
		}
		
		long count = 0;
		for(int i = 0; i<(max-min+1); i++) {
			if(check[i]==false) {
				count++;
			}
		}
		System.out.print(count);
		
		
		
	}
}

 

 

에라토스테네스의 체 알고리즘을 바탕으로 접근한다.

예를 들면, 1을 제외한 가장 작은 제곱수는 4 이다.

시작 ~ 끝 구간에서 4로 나누어 떨어지는 수를 찾고 

반복문을 통해 그 수에서 4를 더한 수를 제곱ㄴㄴ수로 표기해놓는다.

4에 대한 작업이 끝나면 9에 대한 작업으로 넘어가고...

이런 식으로 코드를 작성하면 하나하나 모두 검사하는 것 보다 훨씬 효율적으로 탐색할 수 있다.

 

문제의 예시처럼 min으로 1 max로 10이 들어왔다고 하자.

min값으로 주어진 1 을 첫번째 제곱수인 4로 나눠 몫을 구한다. (몫은 0)

0에다가 현재 체크하고있는 제곱수인 4를 곱해주면 0인데 0은 1~10 사이에 들어가지 않는다.

잠시 4를 생각해보자. 4를 현재 체크하고 있는 제곱수인 4로 나눈 몫은 1이고, 1에 4를 곱하면 4이고.. 이 수는 1~10 사이에 들어간다.

즉, min 값 / 현재 체크하고 있는 제곱수가 나누어 떨어지면 몫을 가져가고

나누어떨어지지 않으면 몫에 1을 더한 값으로 가져간다.

 

제곱수로 나눠지는 수가 몇 개 있는지 확인하는 배열로 boolean 타입의 배열을 만들어주고

이전에 구한 값부터 시작해 에라토스테네스의 체 느낌으로 제곱ㄴㄴ수를 체크해준다.

 

에라토스테네스의 체를 응용해야 하는 문제여서.. 생각하기가 좀 힘들었다.