프로그래머스 136798. 기사단원의 무기

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

프로그래머스

 

#include <string>
#include <vector>
#include <math.h>
using namespace std;

int solution(int number, int limit, int power) {
    int answer = 0;
    for(int i = 1; i <= number; ++i) {
        int cnt = 0;
        int sqrtI = sqrt(i);
        
        for(int j = 1; j <= sqrtI; ++j)
            if(i % j == 0)
                cnt += j * j == i ? 1 : 2;
        answer += cnt > limit ? power : cnt;
    }
    
    return answer;
}

 

두 번째 for문에서 1부터 i까지의 모든 값을 돌려고 하면 시간초과가 난다.

약수의 개수를 구할 때는 절반까지만 반복문을 돌려도 된다.

 

코드 상에서

i를 j로 나눴을 때 0이 될 경우,

i의 제곱근이 j와 같으면 cnt에 1을 더하고 아니면 2를 더한다.