[프로그래머스 - lv1] 기사단원의 무기 파이썬

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/136798

프로그래머스

---

문제 풀이)

이 문제에서 핵심은 각 기사단원의 약수의 시간복잡도를 어떻게 해결할 것인가였다.

일반적인 약수 구하기 방식을 구현하면 시간복잡도 O(N^2)이 된다.

cnt = 0
for i in range(num+1):
	if num % i == 0:
    	cnt += 1

이런식으로 구현하게 되면 만약 위에서 기사의 수 최대 범위인 100000이 되었을때 100000^2이 되어 제한시간을 초과하게 될것이다. 보통 이럴때 약수를 구하는 시간복잡도를 계산하기 위해 내가 약수를 구해야 하는 수의 제곱근까지 탐색을 하면 해결할 수 있다.

따라서 약수의 개수를 수정한 로직은 다음과 같다.

def get_div_num(num):
        cnt = 0
        for i in range(1, int(num ** (1/2)) + 1): # 제곱근까지만 탐색
            if num % i == 0:
                cnt += 1
                if i ** 2 != num: # 만약 해당수의 제곱근까지 약수라면 갯수에 추가
                    cnt += 1
        return cnt

이렇게 구하게 되면 제곱근까지 탐색을 한 후 나머지 쌍으로 이루어진 수는 자동으로 약수의 개수에 포함되게 된다. 좀더 자세한 수학적 증명이 궁금하다면 아래 링크를 통해 읽어보면 될 것 같다.

https://doodle-ns.tistory.com/32

[노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다.

전체 코드

def solution(number, limit, power):
    answer = 0
    def get_div_num(num):
        cnt = 0
        for i in range(1, int(num ** (1/2)) + 1):
            if num % i == 0:
                cnt += 1
                if i ** 2 != num:
                    cnt += 1
        return cnt
    
    knights = []
    for i in range(1, number+1):
        knights.append(get_div_num(i))
    for knight in knights:
        if knight <= limit:
            answer += knight
        else:
            answer += power
    return answer