Algorithm
기사단원의 무기 / 프로그래머스
김예나
2025. 3. 4. 11:28
첫 번째 시도
- 시간초과로 실패!
def solution(number, limit, power):
ans = 0
for i in range(1, number + 1):
cnt = 0
for j in range(1, i + 1):
if cnt > limit:
break
if i % j == 0:
cnt = cnt + 1
if cnt > limit:
ans = ans + power
else:
ans = ans + cnt
return ans
탐색 범위를 제곱근까지만 구하기
- 약수는 짝이 맞춰서 있기 때문에 제곱근까지만 탐색해도 해당 값의 약수의 갯수를 모두 구할 수 있음
- 예시 : 20의 약수를 구하고 싶다
- 1은 20의 약수 : 20 / 1 = 20 -> 20도 20의 약수
- 2는 20의 약수 : 20 / 2 = 10 -> 10도 20의 약수
- 4는 20의 약수 : 20 / 4 = 5 -> 5도 20의 약수
- 20의 제곱근(4.xx)까지만 탐색해도 모든 약수 [1, 2, 4, 5, 10, 20]을 모두 구할 수 있음
- x가 N의 약수라면 N / x 도 N의 약수이다
정답
- 제곱수인 경우 중복되는 경우를 제외하기 위해서 if j != n // j: 조건 추가
- 16의 약수를 구하는 경우 첫번째로 구한 약수는 4이고 그와 대응하는 약수를 구할 때 해당 대응 약수도 4이므로 중복 카운트 방지
def solution(number, limit, power):
ans = 0
for i in range(1, number + 1):
cnt = 0
for j in range(1, int(i ** 0.5) + 1):
if cnt > limit:
break
if i % j == 0:
cnt = cnt + 1
if j != i // j:
cnt = cnt + 1
if cnt > limit:
ans = ans + power
else:
ans = ans + cnt
return ans