C++에서 숫자의 공손도(Politeness) 구하기

이 문제에서는 양의 정수 N이 주어지고, 우리의 목표는 이 숫자의 공손도(politeness)를 구하는 것입니다.

공손한 수(Polite Number)란 두 개 이상의 연속된 자연수의 합으로 표현할 수 있는 수를 의미합니다.

숫자의 공손도는 그 수를 연속된 정수의 합으로 나타낼 수 있는 서로 다른 방법의 개수로 정의됩니다.

예제를 통해 문제를 살펴보겠습니다.

입력

n = 5

출력

1

설명

2 + 3 = 5 가 유일한 연속 합 표현입니다.

해결 접근 방법

가장 직관적인 해결책은 N 이하의 모든 연속 수열을 하나씩 검사하여 그 합이 N과 일치할 때마다 카운트를 늘리는 것입니다. 이 카운트가 바로 해당 숫자의 공손도가 됩니다.

다만 이 방법은 효율적이지 않습니다. 더 복잡하지만 훨씬 효율적인 방법은 소인수분해를 활용하는 것입니다. 숫자의 공손도는 '홀수 약수의 개수 − 1'과 같으며, 이를 소인수의 지수로 표현하면 다음 공식이 성립합니다.

N = a^x × b^y × c^z … (소인수분해 형태)일 때
공손도(Politeness) = (x + 1) × (y + 1) × (z + 1) × … − 1

여기서 2의 거듭제곱 부분은 홀수 약수의 개수에 영향을 주지 않으므로, 계산 전에 미리 제거해도 무방합니다.

예를 들어, 15는 1+2+3+4+5 = 4+5+6 = 7+8 처럼 세 가지 방법으로 표현할 수 있으므로 공손도는 3입니다. 실제로 15의 홀수 약수는 1, 3, 5, 15로 네 개이며, 4 − 1 = 3으로 공식과 정확히 일치합니다.

풀이 코드 예시:

예제

#include <iostream>
using namespace std;
int calcPolitenessNumber(int n){
    int politeness = 1;
    // 2로 나누어 떨어지는 만큼 제거 (홀수 약수 개수에는 영향 없음)
    while (n % 2 == 0)
        n /= 2;
    // 남은 수의 홀수 소인수들의 지수를 조사
    for (int i = 3; i * i <= n; i += 2) {
        int divCount = 0;
        while (n % i == 0) {
            n /= i;
            ++divCount;
        }
        politeness *= divCount + 1;
    }
    // 마지막에 남은 수가 2보다 크면 지수 1짜리 홀수 소인수
    if (n > 2)
        politeness *= 2;
    return (politeness - 1);
}
int main(){
    int n = 13;
    cout<<"Politeness of "<<n<<" is "<<calcPolitenessNumber(n);
    return 0;
}

출력

Politeness of 13 is 1

위 코드는 √N까지만 검사하므로 시간 복잡도가 O(√N)으로, 완전 탐색 방식보다 훨씬 빠르게 동작합니다. 예제의 13은 6 + 7로만 표현할 수 있으므로 공손도가 1로 출력됩니다.