[Baekjoon]백준 13909 창문 닫기(실버 5) - Python

문제설명

예제

문제를 살펴보면 창문이 열려있으면 닫고, 닫혀있으면 열면 되는 아주 간단한 문제처럼 보인다

처음에 든 생각은 약수, 배수 문제이긴 하지만 그냥 배수를 활용하여 리스트를 만들고 리스트에서 

창문을 닫혀있다면 열고 열려있다면 닫는 코드를 작성하면 되지않을까 라는 생각으로 

간단하게 코드를 작성하였다

n = int(input())
window = [0] * (n + 1)

def open_close(n, data):
    for i in range(n, len(window), n):
        if data[i] == 0:
            data[i] = 1
        else:
            data[i] = 0
    return data
            
for i in range(1, n + 1):
    open_close(i, window)
    
print(window.count(1))

리스트에 window의 상태를 저장하고 이를 반대로 전환해주는 코드를 작성하였더니 메모리 초과가 발생하였다

문제를 다시 보니 문제의 메모리 제한이 64mb로 평소보다 작았고 그로 인해 발생한 문제인 것 같았다

약수, 배수, 소수와 큰 관련이 존재하는 것으로 추정하여 일단 window의 각 값에 따라 변화하는 

상태를 확인해보았더니 규칙성이 발견되었다

1의 수가 각 제곱근의 수만큼 증가하는 것을 발견할 수 있었다

다시 말해 1~3 일때는 1, 4~8 일때는 2 와 같은 방식으로 확인할 수 있었다

그러면 정답 코드는 상당히 간단해진다

n = int(input())
print(int(n**(0.5)))