[프로그래머스] 약수의 개수와 덧셈 c++

문제 설명

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ left ≤ right ≤ 1,000

입출력 예

left	right	result
13	17	43
24	27	52

풀이

#include <string>
#include <vector>

using namespace std;

int solution(int left, int right) {
    int answer = 0;
    
    for(int i = left; i <= right; i++){
        int cnt = 0;
        for(int j = 1; j <= i; j++){
            if( i % j == 0 ){
                cnt++;
            }
        }
        if(cnt % 2 == 0)
            answer += i;
        else
            answer -= i;
    }
    
    return answer;
}

다른 풀이

재귀함수로 left 값을 하나씩 올려 약수의 개수를 확인한다.

재귀함수 임으로 결과 값이 right -> left 순으로 리턴된다.

solution 리턴값이 a , (a+1) 두 개씩 계산하여 반환한다. 

재귀함수가 right , right - 1 를 계산하면서 빠져나오게 된다.

int sign(int n, int count = 1) {
    for (int i = 1, last = n >> 1; i <= last; ++i) if (n % i == 0) ++count;
    return count & 1 ? -1 : 1;
}
int solution(int a, int b) { return a > b ? 0 : sign(a)*a + solution(a + 1, b); }