기사단원의 무기 - Python, 약수 찾기

 

 

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

프로그래머스

 

 

풀이 - 나의 생각

약수를 구하는 방법이 중요한 거 같다.

 

가장 좋은 방식은

 

1 ~ number까지의 약수를 미리 구해둔 후 처리하는 방법이 아닐까 생각한다.

 

확실히 그때 그때 약수를 구해서 처리하는 것보다는 빨랐다.

 

i 를 기준으로 i의 배수들에 반복하면서

 

해당 숫자의 약수 개수를 구할 수 있다.

 

이 방법이 하나씩 구하는 경우보다 훨씬 빠르다

코드

 

def solution(number, limit, power):
    weight = 0
    divisors = [0] * (number + 1)
    
    for i in range(1, number + 1):
        for j in range(i, number + 1, i):
            divisors[j] += 1
    
    for i in range(1, number + 1):
        weight += divisors[i] if divisors[i] <= limit else power
            
    return weight

 

 

def divisors(n, limit, power):
    cnt = 0
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            cnt += 2 if i != n//i else 1
        
    return cnt if cnt <= limit else power

def solution(number, limit, power):
    weight = 0
    for n in range(1, number + 1):
        weight += divisors(n,limit, power)
            
    return weight

 

 

 

 

 

다음에 또 봐요