프로그래머스 12928 - 약수의 합 (Lv.1)

출처: https://school.programmers.co.kr/learn/courses/30/lessons/12928

// 프로그래머스 12928 - 약수의 합 (Lv.1)
// https://school.programmers.co.kr/learn/courses/30/lessons/12928

// 문제 설명
// 정수 n을 입력받아 n의 약수를 모두 더한 값을 return 한다.

// 제약 조건
// n은 0 이상 3000 이하인 정수

// Example
// Input : 12   Output: 28   (1 + 2 + 3 + 4 + 6 + 12)
// Input : 5    Output: 6    (1 + 5)

// 접근 — 약수는 짝으로 나온다 (i, n/i)
// n <= 3000이라 1부터 n까지 훑는 O(n)으로도 통과하지만, 약수의 짝 성질을 쓰면 O(sqrt n).
// 1) i가 n의 약수면 n / i도 반드시 약수다. 두 값의 곱이 n이므로 한쪽은 항상 sqrt(n) 이하.
//    따라서 i를 1부터 sqrt(n)까지만 돌면서 i와 n/i를 같이 더하면 모든 약수를 덮는다.
// 2) i * i == n인 완전제곱수는 i와 n/i가 같은 수라서 두 번 더하면 안 된다. 이때만 i 하나만 더한다.
// 3) 경계: n = 0이면 i * i <= 0 이 처음부터 거짓이라 루프가 안 돌고 0을 반환 —
//    "0으로 나누기"에 닿지 않는다. n = 1이면 i = 1에서 i * i == n 분기로 1만 더해 정답 1.
// 4) 조건은 i * i <= n으로 쓴다. sqrt(n)은 실수 오차로 완전제곱수 경계를 놓칠 수 있다.
// 시간 O(sqrt n), 공간 O(1)

#include <string>
#include <vector>

using namespace std;

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

    for (int i = 1; i * i <= n; i++) {
        if (n % i != 0) continue;

        if (i * i == n) sum += i;         // 완전제곱수의 가운데 약수는 한 번만
        else            sum += i + n / i; // 짝을 한 번에 처리
    }

    return sum;
}

정리

• 핵심은 약수가 항상 곱해서 n이 되는 짝으로 나온다는 성질이다. i * (n / i) == n이므로 두 값 중 하나는 반드시 √n 이하 — 즉 √n까지 훑으면 작은 쪽을 전부 만나고, 큰 쪽은 n / i로 즉시 따라온다. n=3000이면 3000회 순회가 54회로 줄어든다. 짝 열거는 “약수를 세는/더하는” 모든 문제에 그대로 적용되는 도구다.
• 제약이 n ≤ 3000이라 1부터 n까지 훑는 O(n)도 그냥 통과한다. 그래도 √n으로 쓰는 이유는 성능이 아니라 확장성 — 같은 골격이 소수 판정(약수가 1과 n뿐인가)과 에라토스테네스 이전 단계의 기본 도구이고, n이 10⁹ 수준으로 커지는 변형에서 O(n)은 즉시 무너진다. 제약이 느슨할 때 더 좋은 골격을 연습해 두는 쪽이 남는 장사.
• 완전제곱수 중복이 유일한 함정이다. n=36에서 i=6일 때 n / i도 6이라 짝 처리를 그대로 적용하면 6을 두 번 더해 정답 91이 97이 된다. i * i == n 분기 하나로 막는다. 짝 열거를 쓰는 순간 “짝의 두 값이 같아지는 지점”을 반드시 따로 처리해야 한다는 게 이 패턴의 고정 비용.
• 루프 조건을 i <= sqrt(n)이 아니라 i * i <= n으로 쓴다. sqrt는 부동소수점 연산이라 완전제곱수 경계에서 결과가 아주 미세하게 작게 나오면 마지막 i를 놓치고, 그러면 가운데 약수가 통째로 빠진다. 정수 비교로 바꾸면 오차가 개입할 여지가 없다.
• 경계 검증: 제약이 “0 이상”이라 n=0이 유효 입력이다. i * i <= 0이 처음부터 거짓이므로 루프가 한 번도 돌지 않고 0을 반환한다 — n % i의 i가 0이 되는 경우가 없어 0으로 나누기에 닿지 않는다. n=1은 i=1에서 i * i == n 분기를 타 1만 더해 정답 1. 두 경계가 모두 분기 추가 없이 자연히 맞는다는 점을 실제로 확인하고 넘어가는 게 중요하다.
• 자료형: n=2880에서 약수합 9906이 3000 이하 구간의 최댓값이다. 약수합 σ(n)은 n보다 클 수 있지만(과잉수) 배수 수준이라 int 여유가 충분하다. 관련 계열 — 77884 약수의 개수와 덧셈은 이 함수의 “개수” 버전을 짝 열거로 세는 문제이고, 12940 최대공약수와 최소공배수는 약수를 열거하지 않고 유클리드 호제법으로 우회한다. 약수를 나열해야 하는가, 나눗셈 관계만 필요한가가 두 계열의 갈림길.
• 검증: 예제 2개(28, 6)와 경계 케이스 n=0(→ 0), n=1(→ 1), 완전제곱수 n=36(→ 91), 상한 n=3000(→ 9360) 통과. 추가로 1부터 n까지 전부 훑는 독립 구현을 따로 만들어 n=0..3000 전 구간 3001개를 대조해 전부 일치함을 확인 (MSVC /std:c++17 컴파일·실행).

핵심 요약 — 약수는 곱해서 n이 되는 (i, n/i) 짝으로 나오므로 √n까지만 훑고 큰 쪽을 n / i로 따라오면 O(√n)이다. 대가는 완전제곱수에서 짝의 두 값이 같아지는 지점(i * i == n)을 따로 처리하는 것, 그리고 루프 조건을 sqrt 대신 i * i <= n 정수 비교로 쓰는 것.