기사단원의 무기

문제 설명

 

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

프로그래머스

숫자 나라의 기사가 1부터 n까지 주어져 있을때, 각 기사는 자신 번호의 약수의 개수 만큼 공격력이 있는 무기를 가질 수 있다. 그러나 이웃 나라와 맺은 협정 때문에 만일 공격력이 한계를 벗어난다면, 해당 무기 대신 협약 기관에서 정한 공격력의 무기를 가져야 한다.

 

공격력 1에 철이 1kg만큼 필요하다. 이때 1부터 n까지의 기사들이 가질 수 있는 무기 공격력의 합을 구하라. 즉, 만들 수 있는 철의 총 무게를 구하는 문제다.

 

문제 풀이

첫 번째 접근

일단 각 기사단원의 번호에 따라 약수를 구해주고 해당 약수의 수만큼 한계를 벗어나는지 확인한다. 벗어난다면 협약 기관에서 정한 한계를 더해주면 되고 아니면 해당 무기의 공격력을 더해주면 된다.

 

그러나 여기서 주의해야 할 점이 약수 계산이다. n의 최댓값은 100,000으로 1부터 n까지 반복문을 계속 돌려서 약수를 찾으면 시간 초과가 일어난다. 그러므로 약수를 계산할 때 범위를 줄여서 시간 초과를 방지해야 한다.

두 번째 접근

약수를 구할 때 시간 초과를 방지하려면 n에다가 루트를 씌운 값까지를 범위로 지정하면 된다. 16의 약수를 구하고 싶으면 1부터 16까지 계산하는 것보다 1부터 4까지 계산하면 되는 것이다. 각 숫자마다 짝이 있으므로 2씩 늘려주면 되지만, 만일 제곱의 값이 n과 같은 경우에는 짝이 없으므로 1만 늘려야 한다.

 

이렇게 구한 약수의 수를 limit와 비교해서 더 크면 power를 더해주고 더 작으면 그냥 약수의 수를 더해주면 된다.

 

def find(n):
    result = 0
    divisorsList = []

    for i in range(1, int(n**(1/2)) + 1):
        if (n % i == 0):
            result += 1
            if ( (i**2) != n) :
                # i와 짝을 이루는 값 또한 더해줘야 하는데, 제곱값을 피하기 위해
                result += 1
    
    return result
            
def solution(number, limit, power):
    answer = 0
    
    
    # 각 약수를 구한다.
    for n in range(1, number+1):
        tmp = find(n)
        if tmp > limit:
            answer += power
        else:
            answer += tmp
            
    return answer