https://www.acmicpc.net/problem/13909
N 개의 창문이 있을 때, 1의 배수부터 시작해서 창문이 열려있으면(1) 닫고(0), 닫혀있으면(0) 여는(1) 문제.
(나는 이 행위를 토글로 받아들였다)
마지막으로는 열려있는 창문(1)의 개수를 출력해주면 됨.
N이 9일 경우를 대입해보자
✅ 초기 상태
창문 상태: [0, 0, 0, 0, 0, 0, 0, 0, 0]
(모두 닫혀 있음, 0 = 닫힘, 1 = 열림)
👤 1번 사람 (1의 배수 토글)
→ 창문 1~9 전부 토글
[1, 1, 1, 1, 1, 1, 1, 1, 1]
👤 2번 사람 (2의 배수 토글)
→ 창문 2, 4, 6, 8
[1, 0, 1, 0, 1, 0, 1, 0, 1]
👤 3번 사람 (3의 배수 토글)
→ 창문 3, 6, 9
[1, 0, 0, 0, 1, 1, 1, 0, 0]
👤 4번 사람 (4의 배수 토글)
→ 창문 4, 8
[1, 0, 0, 1, 1, 1, 1, 1, 0]
👤 5번 사람 (5의 배수 토글)
→ 창문 5
[1, 0, 0, 1, 0, 1, 1, 1, 0]
👤 6번 사람 (6의 배수 토글)
→ 창문 6
[1, 0, 0, 1, 0, 0, 1, 1, 0]
👤 7번 사람 (7의 배수 토글)
→ 창문 7
[1, 0, 0, 1, 0, 0, 0, 1, 0]
👤 8번 사람 (8의 배수 토글)
→ 창문 8
[1, 0, 0, 1, 0, 0, 0, 0, 0]
👤 9번 사람 (9의 배수 토글)
→ 창문 9
[1, 0, 0, 1, 0, 0, 0, 0, 1]
N이 9일때 열려있는 창문은 1,4,9
개수는 3개
공교롭게도 제곱수들만 창문이 열린다.
왜냐하면 제곱수들은 약수의 개수가 홀수 개인 성질을 가지고 있어서
초기 0인 상태에서 홀수번 토글되어 1이 되는것이다.
제곱수가 아닌 수들은 짝수번 토글되어 0으로 돌아온다.
그렇다면 답은 N을 제곱근해주고 소수라면 내림처리해주면 된다.
해답
import sys
N = int(sys.stdin.readline())
print(int(N**0.5))