C++에서 숫자가 연속된 수의 합으로 표현 가능한지 확인하는 방법

이 글에서는 하나의 숫자를 두 개 이상의 연속된 자연수의 합으로 표현할 수 있는지 확인하는 방법을 알아봅니다. 예를 들어 12는 3 + 4 + 5로 나타낼 수 있으므로 조건을 만족하는 수입니다.

이 문제는 의외로 아주 간단한 방법으로 해결할 수 있습니다. 핵심은 2의 거듭제곱인 수는 연속된 수의 합으로 절대 표현할 수 없다는 성질입니다. 반대로 말하면, 2의 거듭제곱이 아닌 모든 양의 정수는 연속된 수의 합으로 표현할 수 있습니다. 이 원리를 이해하려면 다음 두 가지 사실을 기억하면 됩니다.

• 연속된 두 수의 합은 항상 홀수입니다. 두 수 중 하나는 홀수, 다른 하나는 짝수이기 때문입니다.
• 2ⁿ = 2^(n-1) + 2^(n-1)이 성립합니다. 즉, 2의 거듭제곱은 항상 같은 값 두 개의 합으로만 분해되므로 서로 다른 연속된 수들의 합이 될 수 없습니다.

예제 코드

#include <iostream>
using namespace std;

bool isSumofconsecutiveNumbers(int n) {
    // n이 0이 아니고, 2의 거듭제곱이 아니라면 true 반환
    if((n & (n-1)) && n){
        return true;
    } else {
        return false;
    }
}

int main() {
    int num = 36;
    if(isSumofconsecutiveNumbers(num)){
        cout << "표현할 수 있습니다";
    } else {
        cout << "표현할 수 없습니다";
    }
}

출력 결과

표현할 수 있습니다

코드 설명

위 코드의 핵심은 비트 연산 n & (n-1)입니다. 어떤 수 n이 2의 거듭제곱이라면, n을 이진수로 표현했을 때 최상위 비트 하나만 1이고 나머지는 모두 0입니다. 이때 n-1은 그보다 낮은 자릿수가 모두 1이 되므로, 두 값을 AND 연산하면 반드시 0이 됩니다.

따라서 n & (n-1)의 결과가 0이 아니면서 n이 0이 아니라면, 해당 수는 2의 거듭제곱이 아니라는 뜻이고, 곧 연속된 수의 합으로 표현할 수 있다는 의미가 됩니다. 예제의 36은 11 + 12 + 13으로 표현할 수 있으므로 "표현할 수 있습니다"가 출력됩니다. 반면 8, 16, 32처럼 2의 거듭제곱인 수는 이 함수가 false를 반환하게 됩니다.