[백준 - python] 13909번: 창문 닫기

문제 링크

13909번: 창문 닫기

문제 풀이

print(int(int(input())**(1/2)))

17103 입출력 예시

*key point: 

n = int(input()) 
window = [0 for _ in range(n)]
for i in range(n):
    for j in range(i+1, n, i+1):
        window[j-1] = 1 if window[j-1] == 0 else 0
print(sum(window))

문제를 그대로 푸려고 하면 위와 유사한 알고리즘을 떠올릴 수 있다. 하지만 이렇게 문제를 풀게 되면 메모리 초과가 뜨게 된다. 더 적은 메모리를 사용하기 위해서는 간단한 규칙을 찾아내야 한다.

 

어떤 수의 약수의 개수는 대부분 짝수이다.

ex) 10 의 약수는 1, 2, 5, 10인데 (1, 10), (2, 5) 로 짝을 지어줄 수 있음을 생각해보면 알 수 있다.

이를 통해 알 수 있는 것은 10번째 창문은 10의 약수인 1, 2, 5, 10번째 사람에 의해 열고 닫혀 결국 닫혀 있게 된다.

 

하지만 약수의 개수가 홀수인 수가 있다. 바로 제곱수이다.

ex) 25의 약수는 1, 5, 25로 3개 뿐이다.

 

제곱수번째 창문 만이 홀수번 만큼 열고 닫혀 마지막에 열려 있게 된다는 것이다.

따라서 주어진 문제는 n이하의 제곱수의 개수를 구하라는 것과 같다.

또한 제곱수의 개수는 가장 큰 제곱수의 제곱근과 같다.