[파이썬/python] 백준 13909번 : 창문 닫기(🥈5)

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

 

최종답:

import sys
input = sys.stdin.readline

answer = 0
n = int(input())
i = 1
while i * i <= n:
    answer += 1
    i += 1
print(answer)

 

 

답에 도달하기까지의 오답들:

import sys
input = sys.stdin.readline

n = int(input())

window = {}
for i in range(1,n+1):
    window[i] = 1

for i in range(2,n+1):
    for j in range(i,n+1,i):
        if window[j-1] == 0:
            window[j-1] = 1
        else:
            window[j-1] = 0
print(sum(window.values()))

이론적으로는 답이 나오지만

메모리가 매우 커서 오답이 났다.

이렇게 단순하게 푸는 게 아니라, n이하의 제곱수들만 창문이 열려 있게 된다는 규칙을 찾아서 풀어야 했다.

이 규칙을 찾기 어려워서 구글링의 도움을 받았다^^

다음에 비슷한 문제가 나온다면 제곱수를 기억해야겠다.

 

 

import sys
input = sys.stdin.readline

answer = 0
for i in range(1,int(input())+1):
    if (i ** 0.5) - int((i ** 0.5)) == 0:
        answer += 1
print(answer)

그렇게 해서 써내려간 코드

하지만 시간초과가 났다

 

 

import sys
input = sys.stdin.readline

answer = 0
n = int(input())
for i in range(1,n+1):
    while i * i <= n:
        answer += 1
        break
print(answer)

이 코드도 시간초과가 났다..

시간초과를 해결하기 위하여

for문을 이용하지 않고 while문만 이용하여

i * i가 n보다 크거나 작을 때만 while문을 돌려주는 동안 answer에다가 =+ 1을 해주면 되었다.