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

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

프로그래머스

 

약수를 구하는 아이디어만 떠올리면 쉽게 풀리는 구현 문제입니다.

 

간단히 1부터 n까지 수가 가지는 약수를 카운트 해주고, 주어진 limit보다 큰 경우 limit로 갱신해서 누적합을 만들어 주면 됩니다. 단, 약수를 구할 때는 시간초과를 고려해야합니다. 

n의 약수를 구할 때 1부터 n까지 모든 자연수 x에 대해 1부터 x/2까지 일일히 나누어 떨어지는치를 체크한다면 이 문제의 n이 10만이기때문에 10만 x 5만 = 50억이라는 어마어마한 연산이 필요합니다.

 

약수를 나누어 구하는 대신 1부터 n까지 모든 자연수 x에 대해 자신의 배수들을 모두 찾으면 거꾸로 그 배수는 자신의 약수가 몇개인지를 알 수 있습니다. 이 경우엔 10만개의 수에 대해 10만 ÷ x번 연산을 하게 되고 이 값은 대략 1152620이라고 합니다. (해당 연산이 조화급수로 챗 gpt의 도움을 빌렸습니다.) 위에서 필요했던 50억번의 연산에 비해 0.02%에 불과한 매우 작은 연산입니다.

 

간단히 작성한 코드는 아래와 같습니다. 1 ... n으로 x를 키워가며 x의 배수들마다 1씩 더해주면 그 수들은 x로 나누어 떨어지는 수입니다. 

def solution(number, limit, power):
    answer = 0
    arr = [1] * (number + 1)
    
    for i in range(2, number + 1):
        d = i
        while d <= number:
            arr[d] += 1
            d += i
    
    for i in range(1, number + 1):
        if arr[i] <= limit:
            answer += arr[i]
        else:
            answer += power
            
    return answer

 

 

 

 

리스트 컴프리헨션을 이용해 코드를 좀 더 줄일 수도 있습니다.

def solution(number, limit, power):
    answer = 0
    arr = [1] * (number + 1)
    
    for i in range(2, number + 1):
        d = i
        while d <= number:
            arr[d] += 1
            d += i

    return sum([arr[i] if arr[i] <= limit else power for i in range(1, number + 1)])