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

[프로그래머스] 기사 단원의 무기 바로가기

아이디어

• 그냥 반복문 돌렸더니 시간초과 났다
• 앞으로 약수 구하는 건 무조건 int((n ** 0.5) + 1)까지라고 기억하기! ⭐⭐
• ⚠️ 25같이 약수가 중복되는 것 주의하기!

시간 복잡도

• O(n ** 0.5)

코드

def divisor(n):
    answer = 0
    # 약수 구할땐 무조건 제곱근까지만 구하기
    for i in range(1, int((n ** 0.5) + 1)):
        if n % i == 0:
            answer += 1
            if i ** 2 != n:
                answer += 1
    return answer

def solution(number, limit, power):
    powers = [1]
    result = 0
    
    # 약수의 개수 찾기
    for n in range(2, number + 1):
        powers.append(divisor(n))
        
    # limit을 안넘는거 합치기
    for p in powers:
        if p > limit:
            result += power
        else:
            result += p
    
    return result