60. 기사단원의 무기

 

 

using System;

public class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        int[] numArray = new int[number];
        
        for(int i = 0; i < number; ++i)
        {
            int num = 0;
        
            for(int j = 1; j <= i + 1; ++j)
            {
                if((i + 1) % j == 0) num++;
            }
            
            numArray[i] = num;
        }
        
        for(int i = 0; i < number; ++i)
        {
            if(numArray[i] > limit) numArray[i] = power;
            
            answer += numArray[i];
        }
              
        return answer;
    }
}

위와 같이 N의 약수를 찾을 때, 1~N 모든 수를 탐색하니, 시간초과 오류가 났다. 약수의 개수를 찾을 때, 탐색 범위를 좁힐 수 있는 방법은 소인수 분해를 이용하는 방법, N의 제곱근으로 범위를 좁히는 방법 두가지가 있다.

 

 

소인수 분해를 이용하는 방법

N을 소인수분해하여 각 소수의 지수를 구한 후, 각 지수에 1을 더한 값들을 곱한 후 1을 더하여 약수의 개수를 구한다.
N이 24일 때, 이를 소인수 분해하면 2³ * 3¹이며 각 지수에 1을 더한 뒤 곱하면 (3 + 1) * (1 + 1) = 8로 약수의 개수를 구할 수 있다.

 

N의 제곱근으로 범위를 좁혀 탐색

N이 24일 때 소수는 1, 2, 3, 4, 6, 8, 12, 24이고 24의 제곱근은 약 4.9다.
1에서 4까지만 탐색해도 1 * 24, 2 * 12, 3 * 8, 4 * 6이므로 약수가 8개인 것을 바로 알 수 있다.

N이 다른 수의 제곱일 경우 16을 예로 들면 제곱근은 4다.
1, 2, 4, 8, 16이 약수이며 1 * 16, 2 * 8, 4 * 4로 도출이 가능하다.

위 두 경우를 고려하여 N % i == 0일 때 count에 2를 더하고, N / i == i인 경우에 count를 1 빼는 식으로 함수를 짠다면 시간을 줄일 수 있다.

탐색 범위를 1부터 N까지가 아닌 N의 제곱근 만큼만 탐색하는 방식은 N이 소수인지 판별하는 경우에도 탐색 시간을 줄이기 위해 자주 쓰이는 방식이다.

 

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        int[] numArray = new int[number];
        List<int> numList = new List<int>();
        List<int> numList2 = new List<int>();
        
        for(int i = 0; i < number; ++i)
        {
            double sqrt = Math.Sqrt(i + 1);
            
            for(int j = 1; j <= sqrt; ++j)
            {
                if((i + 1) % j == 0)
                {
                    numList.Add(j);
                    numList.Add((i + 1) / j);
                }                              
            }          
            numList2 = numList.Distinct().ToList();
            numArray[i] = numList2.Count;
            
            numList.Clear();
            numList2.Clear();
        }
        
        for(int i = 0; i < number; ++i)
        {
            if(numArray[i] > limit) numArray[i] = power;
            
            answer += numArray[i];
        }
              
        return answer;
    }
}