[백준/python/6359]만취한 상범

문제: 만취한 상범

요즘 백준 알고리즘의 dp문제집을 풀고있다. 이 문제는 내용이 재밌었다. 만든 사람 천재인 것 같다.

t=int(input())
for _ in range(t):
    n=int(input())
    dp=[0]*(n+1)  #초기값을 0(열려있음)으로 설정
    for i in range(2,n+1):
        for j in range(i,n+1):
            if j%i==0:    
                if dp[j]==0:
                    dp[j]=1
                else:
                    dp[j]=0
    print(dp.count(0)-1)   #dp를 n+1로 설정했기 때문에 -1해준다

이번 문제는 공책에 n=1일때부터 n=4일때까지 시뮬레이션을 해본 후 거의 구현으로 풀었다. 내 코드로도 통과되지만 너무 구현식으로 푼 것 같아서 다 풀고나서 다른 사람의 풀이를 참고해보았다.

from math import floor
t = int(input())
for i in range(t):
    n = int(input())
    print(floor(n ** 0.5))

이렇게 간단하게 풀다니. 도망나간 사람의 숫자에 초점을 맞춘 코드이다.