(Python) *기사단원의 무기 (프로그래머스 Lv.1)/제곱근까지만 범위설정

기사단원의 무기 (프로그래머스 Lv.1)

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

프로그래머스

 

내 코드

def solution(number, limit, power):
    answer = [0]*(number+1)
    result =0 
    
    if number == 1:
        return 1 
    
    for i in range(1,number+1):
        for j in range(1,i+1):
            if i % j == 0:
                answer[i] += 1
                
    for i in range(len(answer)): 
        if answer[i] > limit:
            answer[i] = power
        result += answer[i]
    
    return result

처음에 시간초과가 뜬 코드 

해결하지 못해서,,, 다른 코드를 참고 함

def solution(num, lim, pow):
    div = [1]
    for i in range(2, num+1):
        cnt = 0
        for j in range(1, int(i**(1/2)+1)): #제곱근까지만 범위 설정
            if i % j == 0:
                cnt += 1
                if j**2 != i: #제곱이 되는 약수 중복 방지
                    cnt+=1
        if cnt > lim:
            cnt = pow
            div.append(cnt)
        else:    
            div.append(cnt)
    return sum(div)

 

append를 하는 방식이 좋았다. 처음에 div에 왜 1이 들어간 채로 시작하는 지 이해를 못했었는데, 생각해보니 1은 무조건 들어가니까 미리 넣어두신 거였다. 

i가 제곱수가 아닐때 약수를 2개 잡는 이유는 제곱수일때는 (예를 들어 25) 앞에서 이미 저장해놓은 수가 나머지 짝인 수이기때문이다(5),

약수는 항상 짝을 가지는데, 예를 들어 26이면 2,13처럼 두개의 곱이 26이기때문에 두개가 짝이고, 25의 경우 5,5로 1개의 약수만 나온다. 따라서 제곱수의 경우 짝이 없어서 +1, 아닌경우 짝이 있어서 +2가 되는 것이다.