[알고리즘] 프로그래머스 - 기사단원의무기 Lv.1 (java)

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

프로그래머스

 

Lv.1 이길래 그냥 약수를 for 문돌면서 다구해서 집어넣었더니 시간초과...... 

규칙같은건 안보이고 뭔가 수학적으로 접근해야되는 문제겠다 싶어 약수구하는 방법을 찾아봤더니

제곱근으로 약수를 구하는 방법이 있어 사용했더니 문제가 풀렸다.

 

package Programmers;

public class 기사단원의무기 {
    public static void main(String[] args){
        기사단원의무기 T = new 기사단원의무기();
        int number = 100;
        int limit = 3;
        int power = 2;
        T.solution(number, limit, power);
    }

    public int solution(int number, int limit, int power) {
        int answer = 0;
        for (int i = 1; i <= number; i++) {
            int divisor = divisorCnt(i, limit, power);
            answer += divisor > limit ? power : divisor;
        }
        return answer;
    }

    public int divisorCnt(int target, int limit, int power){
        int cnt = 0;
        for (int i = 1; i <= Math.sqrt(target); i++) {
            if(i*i == target){
                cnt ++;
            }else if(target % i == 0){
                cnt += 2;
            }
        }
        return cnt;
    }
}

number 만큼 기사들이 있는데

각숫자의 약수개수 만큼 공격력의 무기를 갖을수 있고

만약 limit 보다 크면 power 변수로 바꾸는 문제

 

 

1. number 길이만큼 for문을 돈다.

2. number 길이를 divisorCnt 로 넘긴다.

3. (중요) 넘어온 값 'target' 변수를 제곱근을 구한다. 

4. i * i == target 시 cnt ++ 해주는 이유는 중복제거를 위해서 제곱근의 값일때는 한번만 더한다. 이유는 밑에서 설명함

5. target % i == 0 (약수이면 +2 를 해준다.) 

6. 최종적으로 계산된 cnt가 limit을 넘는지 안넘는지 확인후 answer에 더해준다.

 

제곱근으로 약수 갯수를 구할수 있는 이유 

target이 100이라고 쳐보자 100의 제곱근은 10 이고 

1 ~ 10까지 수를 100으로 나눠서 나머지를 구해보자.

 

100 % 1 = 0

100 % 2 = 0

100 % 3 = 1

100 % 4 = 0

100 % 5 = 0

100 % 6 = 4

100 % 7 = 2

100 % 8 = 4

100 % 9 = 1

100 % 10 = 0

 

이결과를 통해서 100의 약수는 [1, 2, 4, 5, 10] 을 일단 포함한다는 것을 알수있다.

그리고 여기서 cnt에 2를 더한 이유를 알수있는데 

100에다가 10까지 구한 [1, 2, 4, 5, 10] 을 각각 나눈다.

 

100 / 1 = 100

100 / 2 = 50

100 / 4 = 25

100 / 5 = 20

100 / 10 = 10

 

이렇게 하면 100 의 총 약수가 나온다.

 

[1,2,4,5,10,10,20,25,50,100]

 

그런데 결과를보면 10이 두번 중복된다. 

중복이 나오는 위치는 한번만 계산하기 위해서 i * i == target 일경우는 한번만 값을 더해준것

 

※ Lv.1 이라고 방심하지말자