[ BOJ ] 13909 : 창문 닫기 ( SILVER 5 ) / Python

문제

서강대학교 컴퓨터공학과 실습실 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)이 주어진다.

 

출력

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

풀이 과정

창문이 열리고 닫히는 과정을 살펴보자.

1번 창문 : 열림 (1번째 사람)

2번 창문 : 열림 (1번째 사람) 닫힘 (2번째 사람)

3번 창문 : 열림 (1번째 사람) 닫힘 (3번째 사람)

4번 창문 : 열림 (1번째 사람) 닫힘 (2번째 사람) 열림 (4번째 사람)

5번 창문 : 열림 (1번째 사람) 닫힘 (5번째 사람)

6번 창문 : 열림 (1번째 사람) 닫힘 (2번째 사람) 열림 (3번째 사람) 닫힘 (6번째 사람)

7번 창문 : 열림 (1번째 사람) 닫힘 (7번째 사람)

8번 창문 : 열림 (1번째 사람) 닫힘 (2번째 사람) 열림 (4번째 사람) 닫힘 (8번째 사람)

9번 창문 : 열림 (1번째 사람) 닫힘 (3번째 사람) 열림 (9번째 사람)

...

 

창문이 열리고 닫히는 과정을 구하다보면, n번 창문을 열고 닫는 사람은 n의 약수 번째 사람임을 알 수 있다.

그렇기에, n의 약수 개수가 홀수일때 창문은 열리고, n의 약수 개수가 짝수일때 창문은 닫힌다.

 

우리는 열려 있는 창문의 개수를 출력해야 하기에 약수 개수가 홀수인 n을 찾아야 한다.

약수 개수가 홀수인 것은 바로 제곱수이다!

 

6, 8, 15 와 같이 일반적으로 약수들은 다른 약수와 짝지어져 곱해진다.

6 : ( 1x6 / 2x3 )

8 : ( 1x8 / 2x4 )

15 : ( 1x15 / 3x5 )

 

자기 자신과 곱해져 만들어지는 제곱수는 약수의 개수가 홀수이므로 마지막에 열리는 창문은 제곱수 번째 창문이다.

반복문을 이용하여 1 ≤ N 사이의 제곱수 개수를 찾아주면 된다.

import sys
input = sys.stdin.readline

n = int(input().rstrip())

cnt = 0
now = 1
while now**2 <= n:
    cnt += 1
    now += 1

print(cnt)