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

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

프로그래머스

문제 요약 : 기사단의 각 기사는 번호를 가진다. 그 번호의 약수 개수만큼의 공격력을 가진 무기를 구매할 수있다. 그러나 이웃나라와 협약으로 인하여 공격력이 제한 수치 이상이 되게 되면 협약기관에서 정한 공격력을 가지는 무기를 구매해야한다. 무기를 만들 때 무기의 공격력 1당 1kg의 철을 사용한다. 무기를 모두 만들기 위해 필요한 철의 무게를 구하라

 

 

풀이 )

처음에 그냥 무작정 약수를 구하게 했다가 시간 초과가 떴다.

모든 경우를 탐색하게 되면 O(N)의 시간 복잡도를 가지게 된다.

 

약수개수를 구할 때 시간 초과를 줄이는 방법은 제곱근이다.

 

100의 약수를 구해보겠다.

√100 = 10이기 때문에 1~10까지 수에서 100이 0으로 나누어 떨어지는 것을 구해보자.

1, 2, 4, 5,  10이 있다.

이 값을 가지고 100에 나눈다.

100, 50, 25, 20, 10 이있다.

 

즉 제곱근 값만 구하면 나머지 값까지 다 돌려보지 않아도 쌍을 통해 약수를 구할 수 있다. 

이 방법은 O(√N) 시간 복잡도를 가지게 된다.

 

 

코드 수를 줄이고자 문제에서 number은 1이상인 값이 주어지기 때문에 1일 경우에는 구하지 않고 바로 출력할 수 있도록 answer을 1부터 시작하고  for문을 2부터 돌렸다.

 

또한 9의 경우 1,3,9로 3이 두번 반복된다. 그래서 이런 경우를 나누어  count를 +1해주는 값과 +2 해주는 값으로 나누었다.

def solution(number, limit, power):
    answer = 1
    for i in range(2,number+1):
        count = 0
        for j in range(1,int(i**(1/2))+1):
            if i%j == 0 :
                if j == i//j:
                    count += 1
                else :
                    count += 2
            if count > limit :
                count = power
                break
        answer += count
    return answer