백준 : 13909번 창문닫기 [파이썬, 수학, 실버5]

문제

서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.  2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.

예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,

1. 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2. 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3. 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)

결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.

입력

첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.

출력

마지막에 열려 있는 창문의 개수를 출력한다.

 

예제 입력 

3

예제 출력 

1

 

 

[문제 풀이]

import math

n = int(input())

print(math.floor(math.sqrt(n)))

 

너무 어려워서 참고한 설명 첨부

+ 

n번째 창문은 n의 약수의 개수에 따라 열리고 닫히게 된다.

 

 n의 약수의 개수가 홀수개이면 마지막에는 열리게 되고, 짝수개라면 마지막 상태는 닫힌 상태가 된다. 

약수가 짝수개인지, 홀수개인지 어떻게 알 수 있을까? 

 

어떤 수 n의 약수를 구해보면, 일단 1이 있을 것이고 그에 상응하는 n이 있을 것이다. 이처럼 어떤 약수x가 있으면 반드시 그에 상응하는 약수(n/x)가 하나 존재한다. 그렇다면 항상 짝수개일 수 밖에 없을까? 

아니다. 바로 어떤 수의 제곱으로 나타낼 수 있는 수는 그렇지 않다. 

 

어떤 수 n이 x의 제곱이라면 n의 약수의 개수는 x를 기준으로 왼쪽, 오른쪽의 약수는 서로 대응되어 짝수개이지만 x는 x자신과 대응되므로 한 개이다. 결국 홀수개가 된다. 

 

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