[프로그래머스][C++] 약수의 합

약수의 합

문제 링크

약수의 합

분석

약수란 어떤 수를 나머지 없이 나눌 수 있는 자연수입니다.
이 약수들을 확인하고 모두 더한 뒤 리턴하면 됩니다.

for 문으로 1부터 n까지 반복하며 브루트 포스로 나눠서 확인해볼 수 있습니다.

조금 더 효율 적인 방법은n / 2를 하는것이 좀 더 효율적이며, 가장 효율적인 방법은 제곱근($\sqrt{n}$)을 사용하는 방법입니다.

브루트 포스 방법과 제곱근을 사용하는 방법 두가지로 풀어보겠습니다.

풀이

브루트 포스 방법

int solution(int n) {
    int answer = 0;
    
    for(int i = 1; i <= n; ++i)
    {
        if (n % i == 0)
        {
            answer += i;
        }
    }
    return answer;
}

---

제곱근을 사용하는 방법

#include <cmath>

int solution(int n) {
    int answer = 0;

    for (int i = 1; i <= std::sqrt(n); ++i)
    {
        if (n % i == 0)
        {
            answer += i;

            if (i != n / i)
            {
                answer += n / i;
            }
        }
    }

    return answer;
}

제곱근의 경우 if문이 중첩된 이유는 약수 쌍을 처리하기 위함입니다.

예시로 n이 12일 경우 1 X 12, 2 X 6, 3 X 4입니다.
이처럼 하나의 약수를 찾으면, 그에 대응하는 짝이 되는 약수가 항상 존재합니다.
즉, i가 n의 약수라면, n / i도 n의 약수입니다.

성능 요약

브루트 포스 방법의 성능은 다음과 같습니다.

테스트 1 〉 통과 (0.01ms, 4.14MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.14MB)
테스트 4 〉 통과 (0.01ms, 4.14MB)
테스트 5 〉 통과 (0.02ms, 4.22MB)
테스트 6 〉 통과 (0.01ms, 3.63MB)
테스트 7 〉 통과 (0.01ms, 4.14MB)
테스트 8 〉 통과 (0.01ms, 4.02MB)
테스트 9 〉 통과 (0.01ms, 4.2MB)
테스트 10 〉 통과 (0.01ms, 4.13MB)
테스트 11 〉 통과 (0.01ms, 4.2MB)
테스트 12 〉 통과 (0.01ms, 3.68MB)
테스트 13 〉 통과 (0.01ms, 4.06MB)
테스트 14 〉 통과 (0.01ms, 4.13MB)
테스트 15 〉 통과 (0.01ms, 3.67MB)
테스트 16 〉 통과 (0.01ms, 4.14MB)
테스트 17 〉 통과 (0.01ms, 4.21MB)

---

제곱근을 사용한 방법의 성능은 다음과 같습니다.

테스트 1 〉 통과 (0.01ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.16MB)
테스트 3 〉 통과 (0.01ms, 3.66MB)
테스트 4 〉 통과 (0.01ms, 4.12MB)
테스트 5 〉 통과 (0.01ms, 4.12MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 4.16MB)
테스트 8 〉 통과 (0.01ms, 4.12MB)
테스트 9 〉 통과 (0.01ms, 4.16MB)
테스트 10 〉 통과 (0.01ms, 4.19MB)
테스트 11 〉 통과 (0.01ms, 3.67MB)
테스트 12 〉 통과 (0.01ms, 4.2MB)
테스트 13 〉 통과 (0.01ms, 3.67MB)
테스트 14 〉 통과 (0.01ms, 4.15MB)
테스트 15 〉 통과 (0.01ms, 3.67MB)
테스트 16 〉 통과 (0.01ms, 4.13MB)
테스트 17 〉 통과 (0.01ms, 4.18MB)