[알고리즘] 프로그래머스 : 기사단원의 무기 - 레벨 1

2023.09.08 풀이

def solution(number, limit, power):
    answer = 0
    arr=[1]*(number)
    # 약수 배열 생성
    for i in range(2, number+1):
        j=1
        while i*j<=number:
            arr[i*j-1]+=1
            j+=1
    
    # 철 무게 계산
    for i in arr:
        if i<=limit:
            answer+=i
        else:
            answer+=power
    return answer

문제 접근
1. 약수 배열 생성
약수들을 담은 배열을 생성해야하는데, 약수의 개수를 구하는 공식 - 소인수분해하여 소인수들의 지수+1 의 곱 보다는, 에라토스테네스 체 알고리즘을 살짝 응용하여 배수들에 +1 씩 해주는 풀이가 더 간편하고 빠를 것이라 판단.
이 과정에서, number가 꽤 큰 수 이므로 이중 반복을 도는 것보다는 제곱근으로 접근하는게 좋을 것 같다고 생각했으나, 구현이 복잡+ 로직이 한 번에 떠오르지않음.
2. 철 무게를 계산
특정 무게 이하냐/초과냐에 따라 더해야하는 요소가 달라지는 로직임을 이해했으나, 구현이 이렇게 쉽다고 ? 하는 생각에 스택/큐 와 같은 자료구조를 떠올려봄.
그러나 배열에 입.출력과 동시에 처리하는게 아니라, 배열에 한번에 다 넣은 후 구현해야하므로.
반복문으로 배열의 인덱스를 하나씩 도는거나/배열에서 하나씩 꺼내는거나 비슷하다는 판단을 통해 반복문으로 구현.

---

다른 풀이

ref : 위의 고민을 한 번에 해결하는 풀이인듯 하다.

def get_cds(n, limit , power):
    cnt = 0
    for i in range(1, int(n**(1/2))+1): # ★포인트1. 제곱근만큼만 반복
        if n%i == 0:
            if i == n//i: # 제곱근일 경우 -> 1개만 카운트하기
                cnt += 1
            else:
                cnt += 2 # 제곱근이 아닐 경우, 2개 카운트 (i, n//i)
        if cnt > limit:  # ★포인트2. 소수의 개수가 limit를 넘어가면
            return power #            강제로 power만큼을 return 
    return cnt

    
def solution(number, limit, power):
    total = 1
    for i in range(2, number+1):
        len_cds = get_cds(i, limit, power)
        total += len_cds

    return total

---

check point

• 약수 개수 셀 때.
  - 제곱근 까지만 세는데, 제곱근이면 +1, 아니면 +2
• 제곱근 떠올리면서 sqrt를 생각했는데, int(n**(1/2))+1 도 방법 !