📌 문제

https://school.programmers.co.kr/learn/courses/30/lessons/136798

📌 풀이

코드

def solution(number, limit, power):
    answer = 0
    
    for num in range(1, number + 1) :
        count = 0 # 각 숫자별 약수 개수
        for i in range(1, int(num ** 0.5) + 1) : # 숫자의 절반만 확인하면 됨
            if num % i == 0 : 
                count += 1
                if  i ** 2 != num : # 거듭제곱이 약수가 아니라면 약수는 쌍으로 존재하기 때문에 한 개 더해줌
                    count += 1
            
        if count > limit :
            answer += power
        else :
            answer += count
        

    return answer

설명

어떤 자연수 N의 약수를 구할 때, 1부터 N까지 나누어 떨어지는지 확인해야 한다. 그런데 이렇게 되면 시간이 매우 오래걸린다. 그래서 약수의 아래와 같은 약수의 특징을 생각해보자.

• 약수는 항상 쌍으로 존재한다.(나누어 떨어진다는 것은 나누는 수와 몫이 있어야 되기 때문)
• 그런데 N이 어떤 수의 제곱수이면 약수는 쌍이 아니라 한 개만 존재한다.(중복이 없어야 하기 때문)
• 약수를 판단할 때 약수는 쌍으로 존재하기 때문에 $\sqrt N$ 까지만 확인하면 된다.

그래서의 개수를 확인할 때(두 번쨰 for) 반복 조건에 num ** 0.5 를 준 것이다.