BOJ 6359번 : 만취한 상범 (Python/Bronze 2)

6359번: 만취한 상범

문제

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. k번째 라운드에서는 번호가 k의 배수인 방이 열려 있으면 잠그고, 잠겨 있다면 연다. 이렇게 n번째 라운드까지 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

구금되어있는 몇 명(어쩌면 0명)의 학생들은 자신의 방을 잠그지 않은 채 상범이가 쓰러져버렸단 것을 깨닫고 즉시 도망친다. 방의 개수가 주어졌을 때, 몇 명의 학생들이 도주할 수 있는지 알아보자.

 

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 한 개씩 방의 개수 n(5 ≤ n ≤ 100)이 주어진다.

 

출력

한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다.

---

예제 입력

2
5
100

예제 출력

2
10

---

문제 설명

빨간문이 열린 문이다. 1라운드이면 1의 배수의 문만 본다. 2라운드 때는 2의 배수의 문만 본다. 2의 배수의 문들이 닫혀있으면 열고, 열려 있으면 닫는다. 나머지 라운드도 이와 같다. 

 

Solution

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    door = [False]*(n+1) #문이 닫혀있는 걸 False로 표현
    cnt = 0 #결과값을 위한 카운트 변수
    for i in range(1, n+1): #라운드
        for j in range(i, n+1): #방
            if j % i == 0: #배수를 찾기 위한 조건문
                if door[j] == False: #문이 닫혀있으면 열기(True로 변환)
                    door[j] = True
                else: #문이 열려있으면 닫기 (False로 변환)
                    door[j] = False
    for k in door:
        if k == True: #방들 중에 열려있는 것만 카운트
            cnt += 1
    print(cnt)

다른 풀이

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

간단한 풀이도 있다. 확실히 윗 코드와 비교해서 짧고 명료하다.