[연습문제] 기사단원의 무기

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

프로그래머스

---

문제 설명
숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다.

기사들은 무기점에서 무기를 구매하려고 합니다.

각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다.

단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.

예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다.

만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다.

무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다.

그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.

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

---

제한사항

• 1 ≤ number ≤ 100,000
• 2 ≤ limit ≤ 100
• 1 ≤ power ≤ limit

---

입출력 예

number	limit	power	result
5	3	2	10
10	3	2	21

---

입출력 예 설명
입출력 예 #1

• 1부터 5까지의 약수의 개수는 순서대로 [1, 2, 2, 3, 2]개입니다.
• 모두 공격력 제한 수치인 3을 넘지 않기 때문에 필요한 철의 무게는 해당 수들의 합인 10이 됩니다.
• 따라서 10을 return 합니다.

입출력 예 #2

• 1부터 10까지의 약수의 개수는 순서대로 [1, 2, 2, 3, 2, 4, 2, 4, 3, 4]개입니다.
• 공격력의 제한수치가 3이기 때문에, 6, 8, 10번 기사는 공격력이 2인 무기를 구매합니다. 따라서 해당 수들의 합인 21을 return 합니다.

---

약수의 개수에 따라서 공격력이 다른 무기를 구매해야 하는 기사들이 있을 때, 이들의 무기를 만들 때 필요한 총 철의 무게는 몇 kg인지 구하는 문제입니다.

 

총 1번부터 number번까지의 약수를 구해야 하는 것이 첫 번째고, 그 약수의 값이 공격력 제한을 넘지 않는지 확인하는 것이 두 번째라고 볼 수 있습니다.

특히 이런 문제에서 약수의 개수를 직접 구해야 하기 때문에 어떻게 약수를 구할 것인지도 생각해야 합니다.

 

약수는 기본적으로 쌍을 이룹니다.

12를 예로 들자면, 1 - 12, 2 - 6, 3 - 4로 총 3쌍, 6개의 약수가 존재합니다.

대략적으로 따지면 절반 정도까지만, 정확히는 √n까지만 확인하면 모든 약수 쌍을 구할 수 있습니다.

이 방법을 사용해서 약수의 개수를 구하고, 무기에 필요한 철이 몇 kg인지 구해보도록 하겠습니다.

 

1. 자바

class Solution {
    public int cnt_div(int number) {
        int cnt = 0;
        // 제곱근까지의 값에 대해 탐색합니다.
        for (int i = 1; i <= Math.sqrt(number); i++) {
            // 나머지가 없다면 약수 쌍이므로 2 증가
            if (number % i == 0)
                cnt += 2;
            // 제곱근이라면 약수 쌍이 아니므로 1 감소
            if (i * i == number)
                cnt -= 1;
        }
        // 약수의 개수를 반환합니다.
        return cnt;
    }
    
    public int solution(int number, int limit, int power) {
        int answer = 0;
        // 1부터 number까지에 대해 탐색합니다.
        for (int i = 1; i <= number; i++) {
            // i의 약수의 개수를 구합니다.
            int wep = cnt_div(i);
            // 약수의 개수가 limit보다 크다면 power로 저장합니다.
            if (wep > limit)
                answer += power;
            // limit보다 작다면 그대로 저장합니다.
            else
                answer += wep;
        }
        // 총 철의 무게를 반환합니다.
        return answer;
    }
}

 

2. 파이썬

def cnt_div(number):
    # 약수의 개수 count
    count = 0
    # √n까지 반복합니다.
    for i in range(1, int(number ** (1/2)) + 1):
        # 나누었을 때 나머지가 0이면 약수쌍이므로 2 증가
        if number % i == 0:
            count += 2
        # 제곱근일 경우 중복되므로 1 감소
        if i ** 2 == number:
            count -= 1
    return count

def solution(number, limit, power):
    answer = 0
    # 1부터 number까지 진행합니다.
    for i in range(1, number + 1):
        # 해당 기사의 약수를 구합니다.
        wep = cnt_div(i)
        # 약수의 개수가 한계보다 크면
        if wep > limit:
            # 지정값으로 저장
            answer += power
        # 아닐 경우 그대로 저장
        else:
            answer += wep
    return answer

 

소수를 판별하는 문제와는 다르게, 약수의 개수를 구하는 문제는 딱히 엄청 효율난 부분이 없습니다.

각각의 수에 대해서 일일이 구해야 하므로, 그나마 제곱근까지만 판별하는 게 가장 효율적이라 할 수 있습니다.