[diamond5] [해설 안봄, 분류x] 1557 제곱 ㄴㄴ

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

 

이 문제를 풀고 나서 조금 황당하고 웃겼던 일이있다. 처음에 이 문제를 풀때  이분탐색으로 풀 생각은 어렵지 않게 했으나,  n 번째의 ㄴㄴ수를 찾는 과정에서 아, 내가 모르는 알고리즘이 있겠구나 하고 참고좀 하려고 구글링을 하였다. 어느 블로그의 글 미리보기에서 '에라토노스의 체' 라는 단어가 언급이 된 걸 보고, 아, 채로 거르는 건가? 하고 다시 한번 자력으로 풀어보려고 낑낑대다 결국 풀었다.  그런데 웃긴 점은 풀고나서 그 블로그를 들어가보니  '에라토노스의 체'는 그분이 단순히 소수를 구할 때 사용한 것이고, 풀이과정은 나와 전혀 다른 것이었다. 채로 거르는 것도 아니었다. (포함배제의 원리를 사용하셨는데, 나중에 시간나면 공부해 봐야겠다.  ) 전혀관련없는 키워드였는데 힌트라 생각하고 풀어서 맞았던게 황당하고 웃겼다.. 이게 플라시보 효과라는 건가.. 

 블로그 풀이과정이 조금이라도 같았으면 해설 확인 으로 올리려 했으나 아예 달랐으므로,, 해설은 안본거로 뒀다.

 

우선 이 문제를 풀때는 이분탐색이라는 것을 어렵지 않게 생각할 수 있을 것이다.  수 N이 있으면 그 수가 몇번째인지 계산이 가능하다면 이분탐색으로 풀 수 있다.  당연히 N이 커질 수록  몇번째인지(K)도 커질 것이기 때문이다. 

 

그렇다면 N일때 몇번째인지 구하는것이 핵심이 될 것이다. 

처음에는 단순히   N에서  소수의 제곱들 4,9,25,49.... 등 으로 나눠서 나온 몫을 빼면 될거라고 생각했다.

소수의 제곱수들의 배수를 빼다보면 채로 걸러져 제곱 ㄴㄴ 수들만 남게 되고  제곱ㄴㄴ수들중 몇번째인지 알게 될 것이다.

 

 

그런데 크나큰 걸 간과했다. 제곱수가 중복해서 지워질 수 있기 때문이다.

어떻게 지워질까 생각좀 하다가 마땅히 떠오르지 않아서 깔끔하게 해설을 보려 서칭하려 했으나, 우연히(?) 힌트가 아닌 힌트를 얻게 되고 채로 거를 생각을 해보게 되었다.

 

 그 결과 한 아이디어가 떠올랐다.

위와같은 상황에서 2의 제곱수인 4의 배수들을 거른 상태라고 하자.  다음차례는 3의제곱수 9를 걸러야 하는데, 문제는 36이 2의제곱수와 중복이 된다.  여기서 이미 2의제곱수를 거른 리스트들에 9 를 곱하면, 중복(4와 9의 공배수들)을 피할 수 있을 것이다.

다시말해 9의 배수들의 갯수를 뺄때는 4의 배수를 거르고 난 수들의 갯수를 빼면 된다.

 

마찬가지로 5의 제곱수 25 를 거를 때는 이미 4와 9 의 배수들을 거른 리스트의 갯수를 빼면 된다.

 

일반화시켜보면 다음과 같다.

 

우선  n -= n / 4 를 한다. 4의 배수의 갯수를 빼는 셈

 

그후 1 부터 n/ 9 까지에서 4의배수 제거된 리스트의 갯수를 뺀다. 9의 배수의 갯수를 빼는 셈

 

마찬가지로... 25의 배수의 갯수를 빼는 셈이다.

 

이렇게 해나가다 보면  n / prime ^ 2 은 1 or 2 or 3 까지 오게 되고 이때는  1이면 1개, 2이면 2개, 3이면 3개를 빼면 된다.

 

이걸 어떻게 구현할 수 있을까?

재귀적으로 풀면 된다.

다음과 같이 재귀적으로 진행할 수 있다. countOrder는 n까지의 수중 prime[1]^2의 배수, prime[2]^2의 배수, ... prime[square]^2의 배수를 제거한 나머지의 갯수다. (square라는 변수 작명센스가 영 좋지 못하다).

isFirst는 만약 n이 제곱수이면 이분탐색 할때 곤란하므로(이분탐색시에는 탐색 포인트가 반드시 제곱 ㄴㄴ 수여야 한다.) 처음 재귀함수가 들어왔을 때 제곱수인지 판별하기 위함이다. 

 

 

 

이제 이분탐색을 해야 하는데 , 이분탐색시에는 만약 이번포인트가 제곱수라면 제곱 ㄴㄴ수가 될때까지 n을 1씩 증가시키게 하였다.

만약 제곱 ㄴㄴ수까지의 간격이 크다면 .. 한번 탐색할 때마다 위의 countORder을 수백번 하게 된다면 시간초과가 날 것이다.

제곱 ㄴㄴ수까지의 간격이 크지않다는 걸 입증하기 위해 다음과 같이 진행하였다.

countORder를 재귀로 만들기 전의 코드이다

돌려놓고 코드를 짜고 있었는데 10분이 지났을 까 ,, 그제서야 count가 10개가 넘는 경우가 한번 나온 걸 보고, 충분히 간격이 좁다는 걸 확인하고 마음놓고 이분탐색을 진행하게 되었다.

 

제곱ㄴㄴ수가 될때까지 중간값 을 증가시켰을 때 K번째 이상일 경우 증가시키기 전의 중간값을 max로 하고, K번째 미만일 경우 증가시킨 후의 중간값을 min으로 하였다. 

다음과 같은 경우 이동전의 mid값이 max가 된다. K와 최대한 가까워져야 되기 때문에 이동전의 mid값을 max로 한다. 만약 이동한 뒤의 값을 max로 두게 된다면 무한반복이 발생할 수 있다.

 

다음과 같이 K가 오른쪽에 있는 경우라면  이동된 제곱ㄴㄴ 수가 더 K에 가깝기 때문에 새로운 min값으로 둔다.

당연히, 이동한 제곱ㄴㄴ 수일때가  k번때라면 탐색을 종료하면 된다.

 

재귀지만 충분히 불필요한 계산을 필터링 하였기 때문에 속도는 푼사람들 사이에서 중위권 정도로 무사히 들어왔다.