[백준] 13909번: 창문 닫기 파이썬

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

문제 설명

창문이 n개 있고, 1번부터 n번까지 번호가 붙어 있습니다. 처음에는 모든 창문이 닫혀있습니다. 어떤 사람이 다음과 같은 규칙으로 창문을 열고 닫습니다.

1. 첫 번째 사람은 모든 창문을 연다.
2. 두 번째 사람은 2의 배수 번호에 해당하는 창문을 연다(이미 열려있으면 닫는다).
3. 세 번째 사람은 3의 배수 번호에 해당하는 창문을 연다(이미 열려있으면 닫는다).
4. 계속해서 n번째 사람은 n의 배수에 해당하는 창문을 열거나 닫는다.

이 과정을 거친 후에, 열려있는 창문의 개수를 구하는 문제입니다.

처음 생각했던 코드

처음에는 모든 창문을 하나씩 살펴보고, n번 사람까지 창문을 열고 닫는 과정을 구현했다. 이를 위해 각 사람마다 창문을 열고 닫는 규칙을 따지며 코드를 작성하려 했다. 하지만 그렇게하면 n의 크기가 너무커서 시간초과가 날 것같았다.. 고민 끝에 제곱수만이 최종적으로 열려 있다는 사실을 알게 되었다.

import sys
n = int(sys.stdin.readline())
count = 1
while True:
    if count**2 <= n:
        count += 1
    else:
        break
print(count-1)

 

더 간단한 풀이

 

import sys
n = int(sys.stdin.readline())
print(int(n ** 0.5))

1. `n ** 0.5`로 `n`의 제곱근을 구합니다.
2. `int()` 함수로 정수 부분만을 남겨서 제곱수의 개수를 출력합니다.