수학 :: 백준 :: 제곱 ㄴㄴ 수 :: 1016

제곱 ㄴㄴ 수

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

[문제 풀이]

min과 max의 범위를 살펴보면, 

    1 <= min <= 1000000000000(10^12) 이고 

    min <= max <= min+1000000 이다.

min의 최댓값이 10^12로 int형 범위(-2147483648 ~ 214783647)를 가볍게 넘어가지만 max의 범위가 min <= max <= min+1000000이기 때문에 문제를 푸는데에는 문제가 없을 것 같다.

  1. 제곱 ㄴㄴ 수인지 체크를 할 (max-min)의 크기를 갖는 배열을 생성한다.

  2. for문 안에서 2부터 차례로 증가시키면서 제곱ㄴㄴ수인지 체크한다.

       여기서 시간을 단축하기 위해, min / (i*i)로 몫을 구한 후 몫을 1씩 증가시키는 방법을 썼다.

  3. 1번에서 생성한 배열을 돌면서 제곱ㄴㄴ수의 개수를 센 후 출력한다.