[프로그래머스] Level 1 - 약수의 합

1. 문제 설명

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 문제

 

2. 풀이

#include <string>
#include <vector>

using namespace std;

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

3. 해설

1부터 n/2 까지 for문을 돌려서, i로 나누어 떨어지는 경우 약수이므로 더해준다.

n/2인 이유는, 자기 자신 n을 제외한 n/2 이상의 약수는 나올 수 없기 때문이다.

따라서 n/2까지만 찾아서 더해준 뒤, 자기 자신을 더하면 약수의 합을 구할 수 있다.

 

---

엄청 돌아가다가 도저히 안 풀려서 인터넷에서 힌트를 보고 푼 문제인데, n/2 이상의 약수가 존재할 수 없다는 사실도 새로 알게 되었다.

Level1도 만만치 않다... 꾸준히 해 봐야겠다.