만취한 상범

6359번: 만취한 상범

 

나의 풀이

import sys

def run_info(room_n, room_info):
    answer = 0
    for i in range(2, room_n + 1):
        for room_key in room_info:
            if (room_key % i == 0):
                if (room_info[room_key] == 1):
                    room_info[room_key] = 0
                else:
                    room_info[room_key] = 1
    
    for i in room_info.values():
        if (i == 1): # 열려 있으면 돔황차
            answer += 1
    return answer

n_ct = int(sys.stdin.readline())
for _ in range(n_ct):
    room_n = int(sys.stdin.readline())
    room_info = {i+1: 1 for i in range(room_n)}
    print(run_info(room_n, room_info))

 

시간 복잡도

for i in range(2, room_n + 1) : 라운드 순회 ( 선형 시간 복잡도 )
    for room_key in room_info : 방을 순회하며 상태 전환 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도는 : 이차형 시간 복잡도 ( O(n**2) )