[LV.3] 연습문제 > 기사단원의 무기 (약수) ⭐️

문제

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

프로그래머스

---

문제 설명

• 1번부터 number까지 번호가 붙은 기사들이 있다.
• 각 기사는 자신의 번호의 약수 개수만큼 공격력을 가진 무기를 구매하려 한다.
• 그러나 공격력이 limit을 초과하면, 그 기사는 공격력 power를 가진 무기를 구매해야 한다.
• 무기의 공격력 1당 철 1kg이 필요하다.
• 모든 기사들이 구매할 무기들의 철 무게 총합을 구하기.
• 제한사항
  1 ≤ number ≤ 100,000
  2 ≤ limit ≤ 100
  1 ≤ power ≤ limit
• 예시
  • number = 5, limit = 3, power = 2
  • 각 번호별 약수 개수:
    1 → 1
    2 → 2
    3 → 2
    4 → 3
    5 → 2
  • 모두 제한 수치 3 이하 → 총합 1+2+2+3+2 = 10
• 결론) 1부터 number까지 각 수의 약수 개수를 구하고, 약수 개수가 limit보다 크면 power로 대체하여 모두 합산

---

정답 코드

def solution(number, limit, power):
    # 1 ~ number 까지 약수 개수 저장용 배열 (초기화)
    divisor_counts = [0] * (number + 1)

    # 1 ~ number까지 모든 수의 약수 개수 구하기
    for i in range(1, number + 1):
        for j in range(i, number + 1, i):
            divisor_counts[j] += 1

    # 철의 무게 계산
    total_weight = 0
    for i in range(1, number + 1):
        if divisor_counts[i] > limit:
            total_weight += power
        else:
            total_weight += divisor_counts[i]

    return total_weight

---

코드 설명

    # 1 ~ number 까지 약수 개수 저장용 배열 (초기화)
    divisor_counts = [0] * (number + 1)

 

 

    # 1 ~ number까지 모든 수의 약수 개수 구하기
    for i in range(1, number + 1):         # ① i: 약수 후보
        for j in range(i, number + 1, i):  # ② j: i의 배수 → i는 j의 약수
            divisor_counts[j] += 1         # ③ j의 약수 개수 1 증가

• 이중 반복문을 이용해 1부터 number까지의 모든 정수의 약수 개수를 효율적으로 계산
• 결과는 divisor_counts[j]에 저장됨

 

    # 철의 총 무게를 저장할 변수 초기화
    total_weight = 0
    
    # 철의 무게 계산
    for i in range(1, number + 1):
        if divisor_counts[i] > limit:
            total_weight += power
        else:
            total_weight += divisor_counts[i]
            
    # 최종적으로 필요한 철의 총 무게를 반환
    return total_weight

• for i in range(1, number + 1):
  • 1번 기사부터 number번 기사까지 하나씩 처리하면서
• 그 수의 약수 개수가 limit보다 작거나 같으면 → 해당 개수만큼 철 추가
• limit 초과 시 → power만큼 철 추가 (제한된 공격력)

 

---

첫 번째 시도 (성공. 효율 개선 필요)

import math

def solution(number, limit, power):
    total = 0
    
    for n in range(1, number+1):
        count = 0
        for i in range(1, int(math.isqrt(n)) + 1):
            if n % i == 0:
                if i == n // i:
                    count += 1
                else:
                    count += 2
    
        if count <= limit:
            total += count
        else:
            total += power
    
    return total

---

코드 일부 설명

for i in range(1, int(math.isqrt(n)) + 1):  # 1부터 n의 제곱근까지 반복
    if n % i == 0:                          # i가 n의 약수인지 검사
        if i == n // i:                     # i가 n의 제곱근과 같다면 (제곱수인 경우)
            count += 1                      # 약수 하나만 추가
        else:
            count += 2                      # i와 n//i 두 개의 약수 추가

 

 

1. range(1, int(math.isqrt(n)) + 1)

• 보통 1부터 n까지 모두 확인하면 O(n) 걸림 → 약수는 짝으로 나타나는 걸 이용
  
  • 예) 12의 약수 : (1, 12), (2, 6), (3, 4)
• 따라서, n의 제곱근까지만 확인해도 충분
  • math.isqrt(n)은 n의 정수 제곱근을 반환해주므로, 1부터 제곱근(n)까지만 반복

2. if n % i == 0:

• i가 n의 약수인지 확인하는 조건

3. if i == n // i:

• i * i == n이면 n은 제곱수
• i가 n의 제곱근과 같은 경우, 약수는 짝으로 두 개가 아니라 하나만 존재
  • 예) 16의 경우 i=4이고 n // i = 4로 같아서, 약수가 (4,4) 한 쌍이 아니라 하나

4. count += 1 또는 count += 2

• i와 n//i가 서로 다를 때는 약수 두 개를 동시에 발견하는 것이므로 count는 2 증가
• 반대로, 제곱수일 경우 count는 1만 증가시켜야 약수를 중복으로 세지 않음

흐름 예시)

• n = 16
  • sqrt(16) = 4
  • 반복: i=1~4
    • i=1: 16 % 1  == 0 → 약수 1,  16/1=16 다름 → count += 2 (1,16)
    • i=2: 16 % 2 == 0 → 약수 2, 16/2=8 다름 → count += 2 (2,8)
    • i=3: 16 % 3 != 0 → pass
    • i=4: 16 % 4 == 0 → 4 == 16//4 → 제곱수 → count += 1 (4)
  • 총 count = 2 + 2 + 0 + 1 = 5

---

개선점

- 약수 개수 미리 구하기

• 현재 방식: 각 숫자마다 약수 개수를 일일이 계산 → O(n × √n)
• 개선 방식: 모든 수의 약수 개수를 한 번에 전처리 → O(n log n) (훨씬 빠름)