[python] 프로그래머스 Lv1 - 기사단원의 무기

🔗 문제 링크

프로그래머스

📁 분류

수학 구현 브루트포스

💡 풀이

주어진 범위 내의 모든 수에 대한 약수의 개수를 계산하고, 주어진 limit 값과 비교하여 조건에 따라 power 값 또는 약수의 개수를 선택한 후, 이들의 합을 반환한다.
number의 범위가 1 ~ 100,000이기 때문에, 시간 복잡도를 개선하기 위해 약수의 개수를 계산할 때 제곱근까지만 반복하여 약수를 계산한다.

💻 코드

def get_divisor_cnt():
    divisor = [0 for _ in range(100001)]

    for n in range(1, 100001):
        for i in range(1, int(n ** (1 / 2)) + 1):
            if n % i == 0:
                divisor[n] += 1
                if i != n // i:
                    divisor[n] += 1
    return divisor


def solution(number, limit, power):
    measures = get_divisor_cnt()
    return sum(power if m > limit else m for m in measures[1:number + 1])