백준 6359 - 만취한 상범

2020-12-23

방 개수만큼 라운드를 돌며 해당 라운드 간격만큼 건너뛰어 체크하며 방을 반대로 여닫는 규칙.

최종 라운드 진행 후 열려 있는 방 개수 구하기.

내가 푼 방식

for _ in range(int(input())):
    n = int(input())
    l = [0] * n
    k = 1
    while k <= n:
        for i in range(k-1, n, k):
            if l[i] == 0: 
                l[i] = 1
            else:
                l[i] = 0
        print(l)
        k += 1
    print(l.count(1))

더 쉬운 방식

for _ in range(int(input())):
    n = int(input())
    print(int(n**(0.5)))

※ 열려 있는 방 개수(ans)는 결국 방 개수(n) 기준으로

ans2 <= n < ans+12

(예) 방 1-3개 : 1개 / 방 4-8개 : 2개 / 방 9-15개 : 3개 / …

따라서 열린 방 개수는 방 개수(n)의 제곱근(n**0.5)이다.

DP로 삽질할 필요 없다. 단, DP 원리는 알아야! :)