연습장
3. 기사단원의 무기 본문
문제 해석
[1번기사, 2번기사, 3번기사, 4번기사, 5번기사]
각각에 대해 약수의 값은 고정이다.
-> [1 , [1,2] , [1,3] , [1,2,4], [1,5] ]
그 약수의 갯수를 다음과 같이 나타내며
-> [1, 2, 2, 3, 2]
이때 limit 의 값이 원소의 값보다 클 경우 -> 원소의 값을 power 로 대체한다.
예2 를 통해 다시 이해해보자면
각각의 약수는 다음과 같고
[1, [1,2], [1,3], [1,2,4], [1,5], [1,2,3,6], [1,7], [1,2,4,8], [1,3,9], [1,2,5,10] ]
갯수는 다음과 같으며
-> [1, 2, 2, 3, 2, 4, 2, 4, 3, 4]
limit 가 3 이므로 3보다 큰 원소에 대해서 power 값인 2로 대체한다.
-> [1, 2, 2, 3, 2, 2, 2, 2, 3, 2]
원소의 합은 21로 result 값이 된다.
풀이방법
1. 숫자의 약수 갯수를 구하는 방법 을 알아야하고
2. 그 갯수가 limit 보다 클경우 power 값으로 대체하며
3. 얻어진 값을 모두 더하면 result 가 된다.
# 약수 갯수 구하는 함수
def div_num(num):
n = 0
for i in range(1,num+1):
if num%i == 0:
n += 1
return n
def solution(number, limit, power):
answer = 0
# 각각의 기사에 대해서 진행
for num in range(1,number+1):
# 약수의 갯수를 구하고
gisa_num = div_num(num)
# 비교
if gisa_num > limit:
answer += power
else :
answer += gisa_num
return answer
로직변경
혹시나 했는데 역시나 이중 for 문으로 진행하여 시간초과가 되어버렸다.
이럴때마다 어떻게 해야될지 항상 고민이 된다.
검색을 조금 해본결과
약수를 구하는 로직에 대해서 조금 변화를 줘야할것같다.
100 의 기준 [1,100], [2,50], [4,25], [5,20], [10,10] 와 같이 짝이 되는 수가 있으며
기존 로직의 경우 1-100까지 모두 넣어서 확인해보는데
100의 제곱근인 10까지만 확인해보더라도 원하는 약수의 갯수를 얻을 수 있게 된다.
시간 복잡도는 기존의 로직의경우 O(N**2) 이였는데 -> O(N**3/2) 정도로 바꼈다고 볼 수 있다.
즉 기존의 약수 구하는 로직을
1~N 까지에 대해서가 아닌 -> 1~N의 제곱근까지
추가로 제곱근이 정수일 경우 [10,10] 같은 경우에 대한 예외 처리
# 약수 갯수 구하는 함수
def div_num(num):
n = 0
for i in range(1,int(num**(1/2))+1):
if num%i == 0:
n += 2
# 제곱근이 정수라면
if num**(1/2) == int(num**(1/2)):
n -= 1
return n
def solution(number, limit, power):
answer = 0
# 각각의 기사에 대해서 진행
for num in range(1,number+1):
# 약수의 갯수를 구하고
gisa_num = div_num(num)
# 비교
if gisa_num > limit:
answer += power
else :
answer += gisa_num
return answer
