프로그래머스 - 기사단원의 무기 - C++

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

int solution(int number, int limit, int power) {
    int answer = 0;
    
    for(int i=1;i<=number;i++)
    {
        // 약수 찾기
        int cnt=1;
        int im=i;
        int nC=2;
        int arr[100000]={0,};
        while(true)
        {
            if(im<=1)break;
            if(im%nC==0)
            {
                arr[nC]++;
                im/=nC;
            }
            else
                nC++;
        }
        for(int i=1;i<=nC;i++)
        {
            if(arr[i]!=0)
            {
                cnt*=(arr[i]+1);
            }
        }
        if(cnt>limit)
            cnt=power;
        answer+=cnt;
    }
    
    return answer;
}

 

간단히 number까지의 수들 각각에 대해 약수의 개수를 구하고 그게 limit 이상이면 power를 아니면 약수의 개수르 ㄹ더해서 answer로 리턴하는 문제이다. 

 

1. 단순 무식한 방법으로 해결해보았다. 1씩 수를 증가시키면 나누어떨어지는지 비교하며 약수를 구하였다. 

-> 시간초과로 실패

 

2. 검색해보니 소인수분해를 통해 약수의 개수를 구할 수 있다고 했다. 

그대로 코드로 구현한 것이 위의 코드이다. 

 while문을 통해 2부터 나누면서 그 지수를 구해 해결한다. 1번보다 반복량이 확실히 줄었지만 여전히 

1~n 까지 돌고 더해서 nC까지 다시한번  반복을 하게 되니 통과는 했지만 아슬아슬했다.

number의 범위가 천만,억으로 넘어가면 시간이 오래걸릴 알고리즘이다. 

 

3. ChatGpt에 물어보았다.

반복횟수가 1~n이 아닌 1~루트n 까지이다. 

왜냐하면 루트n 이후에는 이미 나왔던 약수의 짝이기 때문이다. 

역시나 실행시간이 확연하게 줄어들었다. 

#include <string>
#include <vector>

using namespace std;

int solution(int number, int limit, int power) {
    int answer = 0;
    
    for(int i=1;i<=number;i++)
    {
        int cnt=0;
        for(int j=1;j*j<=i;j++)
        {
            if(i%j==0)
            {
                cnt++;
                if(j!= i/j)
                    cnt++;
            }
        }
        if(cnt>limit)cnt=power;
        answer+=cnt;
    }
    
    return answer;
}

 

 

약수를 구하는 법과 같은 상황과 그것을 코딩으로 어떻게 나타낼것인가에 대해선 조금 다른 접근이 필요할때도 있는것 같다.