[백준/Python] 13909: 창문 닫기

[백준/Python] 13909: 창문 닫기

n개의 창문과 n개의 사람이 있다. 처음에 모든 창문이 닫혀 있다.

1번째 사람은 처음에 모든 창문을 연다.
2번째 사람은 2, 4, 6, 8... 번째 창문을 닫는다.
3번째 사람은 3, 6, 9... 번째 창문을 열거나 닫는다.

처음엔 해당하는 수의 약수 개수를 찾으면 몇번 열고 닫고 했는지 알 수 있기 때문에 약수 개수를 구하는 방법을 사용하려고 했다.

1의 약수 : 1 -> 열림
2의 약수 : 1, 2 -> 닫힘
3의 약수 : 1, 3 -> 닫힘
4의 약수 : 1, 2, 4 -> 열림

그래서 아래 코드를 사용하였다.

def divisorCount(n):
    cnt = 0
    for i in range(1, int(n**(1/2))+1):
        if n%i == 0:
            cnt += 1
            if i**2 != n:
                cnt += 1
    return cnt

n = int(input())
Wcnt = 0
for i in range(n):
    if divisorCount(i)%2 != 0:
        Wcnt += 1
print(Wcnt)

divisorCount 함수를 통해 약수 개수를 세는데, for문을 돌면서 약수 개수가 짝수이면 창문에 짝수번 접근이 일어난 것이므로 닫혀있다. 반대로 홀수개이면 열려있을 것이다.

그런데 테스트 케이스 출력은 정상적으로 되지만 위의 코드로는 시간 초과가 난다.

더 쉽게 풀 수 있는 방법이 무엇인가 고민해봤는데, 굳이 약수 개수를 셀 필요 자체가 없었다.

위는 n에 따른 열린 창문의 개수이다.
창문의 개수는 1, 4, 9, 16... 즉, 1, 2, 3, 4...의 제곱 다음부터 변화한다.
이런 결과가 나오는 이유는 직접 창문 개수를 열고 닫는 걸 세어보면 알겠지만 마지막엔 결국 제곱수의 창문만이 열려있게 되기 때문이다.

따라서 4까지는 1의 창문만 열려 있고, 5에서 9까지는 1과 4의 창문만 열려 있고, 10에서 16까지는 1, 4, 9의 창문 3개가 열려 있고... 이런 식이다.

그리고 애초에 약수 개수가 홀수인 수는 제곱수밖에 없었다. (시도는 좋았음)

그러면 최종 코드는 아래와 같다.

소스코드

---

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

뭔가 굉장히 허무한 코드;;

그냥 입력받은 n까지 중에 가장 큰 제곱수의 제곱근을 출력하기만 하면 된다. (24 -> 16 -> 4 출력)