백준 알고리즘 13909번 [창문닫기] 파이썬

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

13909번: 창문 닫기

처음에는 [True, False] 리스트를 만들고 반복문을 돌려 하나씩 열고 닫는 과정을 반복했는데 바로 메모리 부족이 떴다. 아마 문제에서 제기된 n의 범위가 21억이라 그런 거 같다.. 그래서 다른 분들의 풀이를 살펴본 결과 해당 인덱스의 약수의 개수가 홀수이면 창문은 열린 상태이다. 처음부터 창문은 닫혀있으므로 약수가 1개: 열림, 약수가 2개: 열림-닫힘, 약수가 3개: 열림-닫힘-열림.. 이렇게 반복되므로 약수가 홀수이면 되는 것인데 1부터 n까지의 수 중 약수가 홀수인 것을 어떻게 찾냐? 바로 제곱수인 것이다. 10을 예를 들어보면 1x10, 2x5, 10x1 이렇게 총 4개있다. 그러나 25의 경우 1x25, 5x5, 25x1 이렇게 3개뿐이 없는 것을 확인할 수 있다.결국 우리는 1부터 n까지의 범위에서 반복문을 돌려 n을 넘지 않는 제곱수를 찾으면 되는 것이다. 그리고 넘는 순간 반복문을 종료한다. 

n = int(input())

cnt = 0
for i in range(1, n+1):
    if i**2 <= n:
        cnt += 1
    else:
        break

print(cnt)