(JAVA) 백준 1016번 : 제곱ㄴㄴ수

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

1016번: 제곱 ㄴㄴ 수

 

너무 애먹었던 문제.

보통이라면 소수를 찾는 문제들이 대거 있지만

이렇게 소수의 제곱과 나눠떨어지는 문제는 처음봤다.

 

그래서 그런가

정답률이 매우 낮을 뿐 아니라

생각보다 어렵고 까다로운 문제다!

 

 

몇 가지 체크해야 할 부분이 있다.

 

 1) max - min (max와 min의 차이) 는 최소 0에서 최대 1000000(백만)까지이다.

   이는 배열 최대 크기와 근접하므로 최대 길이 1000000인 배열을 사용하는 것을 알 수 있다.

 

 

 2) 제곱ㄴㄴ수는 제곱수로 나눠떨어지지 않는 수 라고 한다.

   제곱수는 정수의 제곱이다.

 

   min의 최대 크기는 100,000,000,000 이고, max의 최대 크기는 min + 1,000,000 이다.

 

   따라서, 제곱수의 크기도 100,000,000,000 이상 가능하기 때문에 

   변수타입 int는 10자리까지밖에 안되므로

   거의 모든 연산에 long 타입을 사용해야 한다.

 

   ** int 숫자 크기 : -2,147,483,648 ~ 2,147,483,647

 

 

 3) 이것 때문에 가장 해매고 시간낭비했었는데,

    제곱수를 구하기 위해 사용하는 코드 i * i 에서

    i의 변수 타입을 int로 설정하고 진행했었다.

 

 그 결과, 인덱스 초과 오류만 계속 나고 뜬금없는 천만 단위 숫자가 연산 결과로 나오게 되었었다..

 int * int 했을 때, 오버플로우(overflow)가 발생했기 때문에 -(마이너스) 값이 나오게 되면서 생긴 에러였던 것이다!

 

 따라서, 제곱근 i의 변수 타입은 작아보여도 long을 사용해야 한다.

  

 

자 그럼

매커니즘으로 넘어가볼까요?

 

 

매커니즘

---

  에라토스체네스의 체 방식을 사용했다.

출처 : 위키백과

 ** 구체적인 정의와 방법은 위키백과 에 자세히 나와있다.

 

 

핵심만 설명하자면

 

예를들어

1 ~ 120 까지의 수 중에 소수를 찾고 싶다!

 

1) 그러면 2부터 시작해서

 

2) 그 수의 배수에 해당하는 숫자들을 전부 찾아서 제거한다.

 

3) 제거되지 않은 숫자들 중 다음 숫자로 넘어간다.

 

4) 다음 숫자의 배수에 해당하는 숫자들을 전부 찾아서 제거한다.

 

5) 11^2 > 120 > 10^2 이므로 11보다 작은 수들의 배수까지만 찾아서 제거한다. ( 120보다 작거나 같은 수 까지 )

 

6) 제거되지 않은 숫자들이 소수!

 

 

 

다시 본론으로 돌아와서,

에라토스체네스의 체 방식을 사용해서

 

1) max - min + 1 만큼의 길이를 가진 boolean 배열을 생성

 

2) max의 제곱근을 구한다.

 

3) 2부터 해당 제곱근까지 반복 진행하는데

 

3-1) 해당 i의 제곱수를 구한다.

3-2) 최솟값부터 시작하므로 min % (i * i) 를 통해

    i.  나누어떨어지면 min / (i * i)의 몫부터 시작해서 몫 * (i * i) 의 값이 max와 같거나 커지기 전까지 반복

    ii. 나누어떨어지지 않으면 min / (i * i)의 몫 + 1부터 시작해서 몫 * (i * i) 의 값이 max와 같거나 커지기 전까지 반복

 을 통해 몫 * (i * i) - min 을 인덱스로 가지는 boolean 배열 원소를 true로 설정한다.

 

4) true 원소 개수 counting

 

5) 끄읏!

 

 

소스 코드

---

// 제곱 ㄴㄴ 수
public class p1016 {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		long min = Long.valueOf(st.nextToken());
		long max = Long.valueOf(st.nextToken());
		
		int result = (int) (max - min + 1);
		int sqrt = ((int) Math.sqrt(max));
		
		boolean[] checks = new boolean[result]; // 제곱 ㄴㄴ수가 아님을 체크. false : 제곱ㄴㄴ수, true : 제곱ㄴㄴ수가 아님.
		long[] num = new long[result];
		 
		
		for(long i = 2; i <= sqrt; i++) { 
				long squared = i * i;
				long start = min % squared == 0 ? min / squared : (min / squared) + 1;
				for(long j = start; j * squared <= max; j ++) {	// 몫을 1씩 증가시킴( j가 몫 )
					checks[(int) ( (j * squared) - min)] = true;
				}
		}
		
		// 제곱ㄴㄴ수 개수 counting
		int count = 0;
		for(int i = 0; i < result; i++) {
			if(!checks[i])
				count++;
		}
		
		System.out.println(count);
	}
}

** 저도 다른 개발자분들의 코드를 참고했습니다..ㅠ

 

 

 

 

깃허브에서 소스코드 보기