[프로그래머스/C++]Lv.1 - 기사단원의 무기

문제 링크

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

내 풀이

number를 최대로 정하고 for문을 돌리면서 약수의 갯수를 구하고 limit를 넘는지 체크하면서 넘으면 power을 넣어주면된다.
약수 구하는 방법은 구글링으로 찾았다.
입력한 숫자의 제곱근까지 for문을 돌리면서 약수를 구하고 그 입력한 숫자에서 그 약수를 나누었을때 자기 자신이 아니라면 ( 약수 * num/약수 = num ) 이 되는 상황이면 약수이므로 ++한다.
시간복잡도는 O(logN)이다.

• https://kbw1101.tistory.com/32

내 코드

#include <string>
#include <vector>
#include <cmath>
#include <iostream>

using namespace std;

int GetDiviser(int num, int limit, int power)
{
    int count = 0;
    for(int i = 1; i <= sqrt(num); i++)
    {
        if(num % i == 0)
        {
            count++;
            if(i != num / i)
                count++;
        }
    }
    cout << count;
    
    return count > limit ? power : count;
}

int solution(int number, int limit, int power) {
    int answer = 0;
    for(int i = 1; i <= number; i++)
        answer += GetDiviser(i,limit,power);
    
    return answer;
}

다른 사람의 풀이

#include <bits/stdc++.h>
using namespace std;

int count(int n) {
    int cnt = 0;
    for(int i=1; i*i<=n; i++) {
        if(n%i) continue;
        if(i*i == n) cnt += 1;
        else cnt += 2;
    }
    return cnt;
}

int solution(int number, int limit, int power) {
    int acc = 0;
    for(int n=1; n<=number; n++) {
        int cnt = count(n);
        acc += (cnt > limit ? power : cnt);
    }
    return acc;
}

다른 사람의 풀이 해석

sqrt를 쓰지 않고도 제곱근까지만 범위를 설정하였다. 또 if문에서 n%i로 한번 거르고 i의 제곱이 n이아니면 cnt를 +2 해준다. 제곱근 이하의 약수는 무조건 곱하면 n이 되는 숫자가 존재하기 때문