문제링크

문제 이해

[ 입력형태 / 조건 ]

number
기사단원의 수를 나타내는 정수 | 5 | 1 ≤ number ≤ 100,000

limit
이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 | 3 | 2 ≤ limit ≤ 100

power
제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 | 2 | 1 ≤ power ≤ limit

[ 문제 ]

=> 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return

[ 풀이 ]

약수의 개수를 구하기 위해 number까지의 수를 각각 곱하면서 카운팅 후 limit보다 넘는 값이면 power로, 그게 아니면 cnt값으로 합

---

코드

> [성공] 1차 시도 : int[] 이용

• 생각한 풀이 그대로 구현

class Solution {
    public int solution(int number, int limit, int power) {
        int[] cnt = new int[number+1];
        for(int i=2; i<=number; i++){
            for(int j=1; i*j<=number; j++){
                cnt[i*j]+=1;
            }
        }
        
        int ans = number;
        for(int i=1; i<=number; i++){
            if(limit <= cnt[i])
                ans += power-1;
            else
                ans += cnt[i];
        }
        return ans;
    }
}

> [성공] 2차 시도 : int[] 이용

• 약수의 개수를 구할때 루트까지만 보고 연산

class Solution {
    public int solution(int number, int limit, int power) {
        int[] cnt = new int[number+1];
        for(int i=2; i<=(int)Math.sqrt(number); i++){
            for(int j=i; i*j<=number; j++){
                if(i==j)
                    cnt[i*j] += 1;
                else
                    cnt[i*j] += 2;
            }
        }
        
        int ans = 2*number-1;
        for(int i=2; i<=number; i++){
            if(limit < cnt[i]+2)
                ans += power-2;
            else
                ans += cnt[i];
        }
        return ans;
    }
}

TIP : 약수 개수를 구하는 방법도 소수를 구하는 방법과 유사하게 구할 수 있다.