[Lv 1] 기사단원의 무기

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

프로그래머스

 

n의 약수를 구해 이 값이 limit보다 크면 power 값으로 대치하면 해결할 수 있다.

단, 약수를 구할 때 n까지 구하게 된다면 최대 값을 때 시간 초과가 발생할 수 있다.

따라서 n을 2로 나눠서 구해야한다.

 

2를 나눠도 올바른 약수의 개수가 구해지는 이유

24 / 2 = 12

12의 약수 : 1 2 3 4 6 12 -> 6

24의 약수 : 1 2 3 4 6 8 12 24  -> 8

즉, 24의 절반 횟수만큼 돌려도 약수는 1 2 3 4 6 8 12까지 구해진다.

마지막에 1을 증가시키면 24의 약수를 구할 수 있는 것

 

#include <string>
#include <vector>

using namespace std;

int calc(int n){
    int num = 0;
    for(int i = 1;i<=n/2;i++){
        if(n % i ==0)
            num++;
    }
    return num + 1;
}

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