약수의 개수와 덧셈

프로그래머스에서 제공한 간단한 수학 문제!
left부터 right까지의 모든 수 중에서, 약수의 개수가 짝수면 더하고 홀수면 빼기만 잘 구현하면 끝나는 문제다.

문제 요약

• 두 정수 left와 right가 주어진다.
• left부터 right까지의 모든 정수에 대해,
• 약수의 개수가 짝수면 해당 수를 더하고, 홀수면 빼서 누적합을 구한다.

예시

입력: left = 13, right = 17

처리:

• 13의 약수: [1, 13] → 2개 → 더함
• 14의 약수: [1, 2, 7, 14] → 4개 → 더함
• 15의 약수: [1, 3, 5, 15] → 4개 → 더함
• 16의 약수: [1, 2, 4, 8, 16] → 5개 → 뺌
• 17의 약수: [1, 17] → 2개 → 더함

최종 결과: 13 + 14 + 15 - 16 + 17 = 43

내 풀이

기본적인 완전 탐색 방식으로 풀었다. 하나씩 직접 약수 개수를 구하면서 더하거나 빼는 단순한 구조다.

#include <string>
#include <vector>

using namespace std;

int solution(int left, int right) {
    int answer = 0;
    int count = 0;

    for (int i = left; i <= right; i++) {
        count = 0;

        for (int j = 1; j <= i; j++) {
            if (i % j == 0) {
                count++;
            }
        }

        (count % 2 == 0) ? answer += i : answer -= i;
    }

    return answer;
}

생각 정리

• 처음엔 그냥 약수 개수를 전부 세면 되겠지 싶어서 단순 반복문으로 구현했음
• 최대값이 1,000이라 성능 걱정은 전혀 없음
• 사실 제곱수만 약수 개수가 홀수라는 걸 알면 더 간단하게 줄일 수도 있음 (다음에 도전해봐야지!)

마무리

간단한 반복문 문제지만, 수학적인 성질까지 생각해보면 더 흥미롭게 접근할 수 있는 문제였다.
약수 개수에 따라 덧셈/뺄셈을 결정하는 로직을 잘 구현했다면, 정답까지 금방 도달할 수 있다!