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

문제 이름 : 약수의 합

1. 문제 설명

2. 약수

이 문제를 그냥 for문을 n번 돌려서 나머지가 0이 나오는 수들을 모두 더할 수 있겠지만 그렇게 하면 최적화가 되지 않고 비효율적이다. 따라서 약수의 성질을 생각해보고 그에 따른 최적화를 생각해봐야 한다. 약수는 자기자신을 어떤수로 나누었을때 나머지가 0이 되는 수를 의미한다. 따라서 다음과 같은 예시를 살펴보자.

1   2   5   10

이는 10의 약수들을 나열한 것이다. 이는 (1, 10) (2, 5) 이렇게 두개씩 짝지으면 두 숫자를 곱했을때 10이 나온다. 이런 성질을 이용하면 두 숫자를 연결할 때 왼쪽에 나올 수 있는 가장 큰 수는 자기자신의 제곱근이다. 따라서 for문을 제곱근 만큼 반복시키면 약수를 모두 탐색할 수 있다.

3. Solution

#include <string>
#include <vector>
#include <cmath>

using namespace std;

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

이 문제는 약수를 모두 더하는 문제이므로 앞에서 설명했다시피 for문을 1부터 n의 제곱근까지 반복시킨다. 그리고 n을 i로 나누었을 때 나머지가 0이면 약수이므로 if문을 넣어주고 그 안에서 원래는 (i, n/i) 이런 쌍을 만들 수 있고 저 두 숫자를 곱하면 n이 된다. 따라서 i와 n/i를 더해주면 된다. 그런데 만약 n이 제곱수인 경우 약수의 개수가 홀수가 되고 예를들어 9면

1   3   9

이런식으로 (1, 9) (3, 3) 이 짝지어지게 되고 이는 약수의 합 문제기 때문에 i와 n/i를 모두 더해주면 1 3 3 9를 더하는 것이기 때문에 n/i가 i가 되면 제곱수이므로 이런 경우에는 i만 더해준다.

4. Review

이 문제는 굉장히 쉬운 문제이지만 제곱근을 이용해 최적화할 수 있는 부분도 존재하고 이렇게 문제를 풀었을 때 제곱수를 예외처리해야 된다는 점에서 초보자와 중급자의 차이가 드러나는 문제인 것 같다.

 

GitHub - leejy811/AlgorithmStudy: 코딩 테스트 스터디