[Programmers / Python 풀이] 기사단원의 무기

def solution(number, limit, power):
    answer = 0
    power_lst = []
    for i in range(1, number + 1):
        cnt = 0
        for j in range(1, int(i**0.5)+1):
            if i % j == 0:
                cnt += 1
                if j**2 != i:
                    cnt += 1
        if cnt > limit:
            answer += power
        else:
            answer += cnt

    return answer

시간초과를 조심해야 하는 문제

 

모든 약수는 짝이 있다. 하지만 그 수의 약수중에 제곱이 그 수와 같은 것이라면 약수는 1개뿐

 

예를 들어 16의 약수들을 보면

1 - 2 - 4 - 8 - 16

1과 16이 짝, 2와 8이 짝 이 되고, 4는 제곱했을 때 16이 된다.

 

그렇다면 결과적으로 for문을 해당 수의 제곱근까지만 순회시키고, 조건문을 통해 약수의 제곱이 그 수와 같지 않다면 기존 1 증가에 1을 더 증가 시켜주면 된다. (반대로 약수의 제곱이 그 수와 같다면 1만 증가 시키는 방식)

 

말로 설명하는게 제일 어렵다..