🖊️ 문제

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

🖊️ 풀이

그냥 1부터 N까지 냅다 돌면서 검색하면 O(N)인데
뭔가 말이 안됨
약수를 구하는 다른 방법이 있을까? 해서 검색했다.

🔥 약수 구하는 방법
1. n의 제곱근 (sqrt(n))을 구한다.
2. 제곱근 이하의 정수 i에 대해 n % i == 0이면 i는 약수
3. n / i도 약수

Skrrrrrrrrrrrrr
개쉽다
앞으로 절대 까먹지 말장!

그리고

제곱근 구하는 함수 : sqrt(n)
라이브러리는 <cmath>를 사용하도록 하자

🖊️ 코드

#include <string>
#include <vector>
#include <cmath>
using namespace std;

int solution(int n) {
    int answer = 0;
    
    vector<int> vec;
    
    double root = sqrt(n);
    for (int i = 1 ; i <= root ; ++i) {
        if (n % i == 0)
            vec.emplace_back(i);
    }
    
    for (auto& v : vec) {
        answer += v;
        
        if (v != n / v)
            answer += (n / v);
    }
    
    return answer;
}