만취한상범

2020-12-23 
layout: post
title: "백준 6359 - 만취한 상범"
author: "asadal"
tags: ["python", "파이썬", "백준", "다이내믹 프로그래밍", "DP", "sqrt"]

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

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

내가 푼 방식

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) 기준으로

ans (2) <= n < ans+1 (2)

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

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

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

문제 보기