C++로 연속된 자연수의 합으로 표현하는 방법의 수 구하기

양의 정수 N이 주어졌을 때, 이 숫자를 하나 이상의 연속된 양의 정수(자연수)의 합으로 나타낼 수 있는 서로 다른 방법이 총 몇 가지인지 구하는 것이 이번 문제의 목표입니다.

예를 들어 입력값이 10이라면 출력은 2가 됩니다. 10은 다음 두 가지 방법으로 연속된 자연수의 합으로 표현할 수 있기 때문입니다.

10 (숫자 자신 하나만 사용)
1 + 2 + 3 + 4

접근 방법

핵심은 N을 i개의 연속된 자연수의 합으로 표현할 수 있는지 판단하는 것입니다. 1부터 i까지의 합은 등차수열 공식에 의해 i × (i + 1) / 2 로 계산됩니다.

N에서 이 값을 뺀 나머지(rem)가 i로 나누어떨어진다면, N은 i개의 연속된 자연수의 합으로 정확히 표현할 수 있습니다. 나머지를 i로 나눈 몫을 b라고 할 때, N = (b + 1) + (b + 2) + ... + (b + i) 형태로 나타낼 수 있기 때문입니다.

또한 어떤 수든 자기 자신 하나만으로 표현하는 방법은 항상 존재하므로, 결과값(ret)은 1에서 시작합니다.

알고리즘 단계

ret := 1 로 초기화합니다.
i를 2부터 시작해 1씩 증가시키며 반복합니다.
- sum := (i × (i + 1)) / 2 를 계산합니다.
- sum > N 이면 반복문을 빠져나갑니다.
- rem := N − sum 을 계산합니다.
- rem이 i로 나누어떨어지면 ret을 1 증가시킵니다.
ret을 반환합니다.

반복 조건은 i(i + 1) / 2 가 N을 초과하는 순간 종료되므로, i는 대략 √(2N)까지만 진행됩니다. 따라서 이 알고리즘의 시간 복잡도는 O(√N)으로 매우 효율적입니다.

다음 예제 코드를 통해 더 잘 이해해 보겠습니다.

예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int consecutiveNumbersSum(int N) {
        int ret = 1;
        for(int i = 2; ; i++){
            int sum = (i * (i + 1)) / 2;
            if(sum > N) break;
            int rem = N - sum; ret += (rem % i == 0);
        }
        return ret;
    }
}; main(){
    Solution ob;cout << (ob.consecutiveNumbersSum(10));
}