[ BOJ ] 6359 : 만취한 상범 ( BRONZE 2 ) / Python

문제

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다.

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

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

방의 개수가 주어졌을 때, 몇 명의 학생들이 도주할 수 있는지 알아보자.

입력

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

출력

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

풀이 과정

1번 방 : 1번 라운드에 열림

2번 방 : 1번 라운드에 열림, 2번 라운드에 잠김

3번 방 : 1번 라운드에 열림, 3번 라운드에 잠김

4번 방 : 1번 라운드에 열림, 2번 라운드에 잠김, 4번 라운드에 열림

5번 방 : 1번 라운드에 열림, 5번 라운드에 잠김

6번 방 : 1번 라운드에 열림, 2번 라운드에 잠김, 3번 라운드에 열림, 6번 라운드에 잠김

7번 방 : 1번 라운드에 열림, 7번 라운드에 잠김

8번 방 : 1번 라운드에 열림, 2번 라운드에 잠김, 4번 라운드에 열림, 8번 라운드에 잠김

9번 방 : 1번 라운드에 열림, 3번 라운드에 잠김, 9번 라운드에 열림

10번 방 : 1번 라운드에 열림, 2번 라운드에 잠김, 5번 라운드에 열림, 10번 라운드에 잠김

11번 방 : 1번 라운드에 열림, 11번 라운드에 잠김

...

 

소수와 합성수는 약수끼리 곱했을 때 짝이 이뤄지는 경우가 존재한다. ( 1 x 12 / 2 x 6 / 3 x 4 )

열리고 잠기는 횟수는 해당 수의 약수 개수만큼이기 때문에, 약수끼리 곱했을 때 짝이 전부 이뤄지는 경우 (약수의 개수가  짝수인 경우) 는 잠기는 경우이다. 

그러나 약수의 개수가 홀수인 경우에는 열리는 경우이다. 이는 제곱수에 해당한다. ( 2 x 2 / 3 x 3 ) 

따라서, 1부터 n까지 범위 안의 제곱수의 개수를 출력한다.

import sys
input = sys.stdin.readline

t = int(input().rstrip())
for _ in range(t):
    n = int(input().rstrip())
    now = 1
    while now**2 <= n:
        now += 1
    print(now - 1)

입력 범위가 작기 때문에 시뮬레이션을 돌려도 무방하다.