기사단원의 무기

프로그래머스 lv1 기사단원의 무기 파이썬

💡 문제

기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력
제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의
공격력을 나타내는 정수 power가 주어졌을 때,
무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 
return 하는 solution 함수를 완성하시오.

🥳 해결!

def solution(number, limit, power):
    result = 0

    for j in range(1, number+1):
        mogi = 0
        for i in range(1, int(j**0.5) + 1):
            if j % i == 0:
                mogi += 1
                if i != j/i:
                    mogi += 1
        if mogi > limit:
            mogi = power
        result = result + mogi

    return result

j의 약수는 최댓값이 j의 루트 값이므로 int(j ** 0.5) +1 로 넣어주고
i가 j*j 인 경우를 제외하고 약수의 개수를 받았다.

처음에 해결하려고 한 방식은,

1. 에라토스테네스의 체와 비슷한 형태를 갖추기
2. 소인수 분해를 어떻게 구현할지 생각해보기
3. ~을 곱한 값의 약수는 ~이다. 를 이용하기.
4. 혹은 모든 약수의 지수 +1 씩 곱한 값은 약수의 개수라는 점을 이용하기

를 적용해 보려했으나, 4는 결국 모든 약수를 구해야하기 때문에 runtime
이 맘에 걸렸고, 3번과 1번을 엮어 만들어 보려 했으나,
구현에 실패해 2번으로만 해결을 했다.

🥔 다른 해결

위도 느린 방식은 아니었지만 개인적으로 찝찝함이 있어서
(처음 접근 방식으로 가고 싶었음... runtime 너무 길어)

찾아보니 질문 칸에 apple1367 님이 작성하신 코드를 봤다.
그래...이거다...당신은 혹시 천..재?

def solution(number, limit, power):
    c = [0 for _ in range(number+1)]
    
    for i in range(1, number+1):
        for j in range(i,number+1,i): # i씩 띄워넘는다. (즉 i의 배수)
            c[j] += 1 # c는 모든 수의 약수 개수
            
    answer = 0
    for i in c[1:]:
        if i <= limit:
            answer += i
        else:
            answer += power
    return answer

print(solution(10, 3, 2))  

미쳤다 이거다....

3. ~에 x를 곱한 값은 그 결과의 약수다.

이걸 나는 계속 나누는 방식으로 생각했는데, list를 만들어서,
for문으로 한번의 루프로 그 1 에서 number+1 까지 i를 곱해서
number + 1까지의 약수를 한번에 리스트에 저장하는 방식..

def solution(number, limit, power):
    c = [0 for _ in range(number+1)]
    
    for i in range(1, number+1):
        for j in range(i,number+1,i): # i씩 띄워넘는다. (즉 i의 배수)
            c[j] += 1 # c는 모든 수의 약수 개수
            
    answer = 0
    for i in c[1:]:
        if i <= limit:
            answer += i
        else:
            answer += power

    return answer

하염없이 대단해...대단하군...대단한데.....를 외치는 나..