[백준] 6359번: 만취한 성범 - python

https://www.acmicpc.net/problem/6359

6359번: 만취한 상범

 

작년 아는 친구 형이 삼성SDS 최종 면접에서 물어봤다고 한 알고리즘

그래서 열심히 풀었다.

 

해보니 나눠지는 약수의 개수가 홀수 개이면 열려있는 걸로 판단하여 아리스토테네스 체를 활용하여 계산한 다음 마지막에 홀수인 것만 카운트 하여 출력하는 로직으로 설계하였다.

T = int(input())

for _ in range(T):
    cnt = 0
    n = int(input()) #n개의 방 0은 닫 1은 열림
    arr = [0] * (n+1)
    #1라운드 1 1 1 1 1
    #2라운드 1 0 1 0 1
    #3라운드 1 0 0 0 1
    #4라운드 1 0 0 1 1
    #5라운드 1 0 0 1 0
    for i in range(1, n+1):
        for j in range(i, n+1, i):
            arr[j] +=1
            
    for k in arr:
        if k % 2 != 0:
            cnt+=1
    
    print(cnt)

 

완성