BOJ 13909 창문 닫기

N개의 창문이 있고, 1번부터 N번까지의 사람이 있고 모든 창문은 닫혀있다.
1번 사람은 1의 배수 번째의 창문들을, 2번 사람은 2의 배수 번째의 창문들을, ..., n번 사람은 n의 배수 번째 창문들을 열려있으면 닫고, 닫혀있으면 여는 행동을 취한다.
1번 사람부터 n번 사람까지 이렇게 했을 때, 마지막에 열려있는 창문의 개수를 구하는 문제이다.

직접 어느정도 해보다 보면 감이 온다.
n번째 창문은 n의 약수의 개수에 따라 열리고 닫히게 된다. n의 약수의 개수가 홀수개이면 마지막에는 열리게 되고, 짝수개라면 마지막 상태는 닫힌 상태가 된다.

약수가 짝수개인지, 홀수개인지 어떻게 알 수 있을까?
어떤 수 n의 약수를 구해보면, 일단 1이 있을 것이고 그에 상응하는 n이 있을 것이다. 이처럼 어떤 약수x가 있으면 반드시 그에 상응하는 약수(n/x)가 하나 존재한다. 그렇다면 항상 짝수개일 수 밖에 없을까? 아니다. 바로 어떤 수의 제곱으로 나타낼 수 있는 수는 그렇지 않다. 어떤 수 n이 x의 제곱이라면 n의 약수의 개수는 x를 기준으로 왼쪽, 오른쪽의 약수는 서로 대응되어 짝수개이지만 x는 x자신과 대응되므로 한 개이다. 결국 홀수개가 된다.

결국 이 문제는 1부터 n까지의 수 중에서 완전 제곱수의 개수를 구하는 문제가 된다.

구현은 여러 방법이 있겠지만.. 음 일단 가장 먼저 생각난 것은 n의 범위가 최대 21억까지인데, 5만 * 5만이 25억이므로 5만부터 대충 5만보다 좀 작은 수에서 시작해서 그 수의 제곱이 주어진 n과 같거나 작아지는 순간을 찾는 방법이나 sqrt(n+1)값을 버림한 정수 값과 그 값에서 1을 뺀 값 중 답을 찾는 방법을 쓰면될 것 같은데.. AC를 받고 다른 분의 코드를 보니 그냥 1부터 시작해서 그 제곱이 n보다 같거나 작은 경우까지 돌리는 경우도 꽤 있는 것 같다.