[JAVA] 백준 1016번 제곱ㄴㄴ수

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

1016번: 제곱 ㄴㄴ 수

우와.. 알고나면 답안이 세상 간단해보이는데, 알기전엔 참 힘든 문제이다.

어느부분이 힘들었냐? 하면 13번째 줄 이라고 단언할 수 있다.

min 값부터 max 값 까지 제곱수로 나누어 떨어지지 않는 수, 즉 제곱수의 배수를 제외 하고 남은 수가 몇개인지를 구하는데...

에라토스테네스의 체를 사용하면 될거같은데.. 문제는 그냥 사용하기에는 max 값이 너무나 크다는 것이었다..

 

힌트는, 문제를 아주 잘 보면, max 값은 크지만 min과 max의 차이는 최대값이 1000001값밖에 나지 않는다는 것이다.

boolean 1차원 배열로 에라토스테네스의 체를 이용할 수 있는 크기이다.

문제는... 어떻게..? min값이 0부터 시작이 아닌데..? ---> 그 부분이 위 소스코드에서 바로 13번째 줄이다.

 

min이 시작하는 값부터 boolean[] d의 index를 0으로 두는 것이다.

예를들어 min이 11부터 시작하고 max가 20이라면 11은 d[0], 12는 d[1], 13은 d[2] ... 20은 d[9]가 된다.

그렇다면, d[0](즉 11 값)은 제곱수랑 나누어떨어지는지 아닌지를 어떻게 아는가? 에라토스테네스의 체를 여기서 어떻게 이용하는가?가 문제이다.

 

2의 제곱수부터 셀 때, 2의 제곱은 4이다. 4의 배수는 모두 지워줘야 한다.

→ d[index](4의배수) 값을 true로 줘서 결과적으로 false인 값의 수를 구한다.(에라토스테네스의 체를 이용)

 

min이 0부터 시작하면, d[4], d[8], d[12] ... d[max]까지 true 값을 줘서 지워주면 된다.

min이 0부터 시작하지 않는데 d[] 에서 index값으로 어떻게 4의 배수인지 구하지?

 

min이 11부터 시작한다고 하면, 11은 d[0]이니깐 12는 d[1], 16은 d[5], 20은 d[9]... 이렇게 갈 것이다.
그렇다면 d[1]이 4의 배수인 것을 찾으면, 그 이후로는 4를 주기로 4씩 증가하는 값을 true로 지워주면 된다.

→ d[1], d[5], d[9]...

 

d[1]이 4의 배수인 것을 어떻게 찾는가?

11은 2의 제곱수인 4로 나누었을때, 나머지가 3이 남는다.

그래서 d[0]인 11은 3부터 시작하고, d[1]값이 4의 배수가 된다. (4-3=1)

그 이후 4씩 더해주는 값(모두 4로 나누었을때 0으로 나누어 떨어지는 값들) 들도 제곱수의 배수에 해당한다.

 

이번에는 3의 제곱수인 9의 배수를 지워보자.

9, 18, 27, 36... 이렇게 지워야 하는데, 18은 d[index]에서 index 값이 어떻게 될까?

11을 9로 나누었을때 나머지는 2이다.

d[0](11)은 9로 나눈 후 2번째에 위치하는 수라면, 9의 배수가 되는 수는 d[7]이 9번째가 되는 수다. (9-2=7)

그 이후는 9씩 더하여 나오는 수를 더해주면 된다. 

→ d[7], d[7+9], d[7+9+9]...

 

즉, d[0]은 min 값이 시작하는 부분이라고 하면 구하고자 하는 제곱수의 배수는

[제곱수 - min값을 제곱수로 나눈 나머지 수] (위 소스코드에서 13번째 줄) 에 해당하는 값이 첫 제곱수의 배수가 되고,

그 이후는 제곱수만큼 더해주는 값들을 지워주는 것이 제곱수의 배수들을 지워주는 것이 된다.

 

또 놓칠 수 있는 한가지는 12번째 줄 for 루트 문에서 int 가 아닌 long 으로 해줄 것!

 

min 값을 제곱수로 나눈 나머지 수가 0 인 경우는 d[0]이 제곱수의 배수가 되므로 변수를 0으로 셋팅해주는 것도 잊지말자!(14~16번째 줄)