문제 정의

자연수 N이 주어졌을 때, 2개 이상의 연속된 자연수 합으로 나타낼 수 있는 경우의 수를 구하라.

예시

• 6 = 1 + 2 + 3

• 9 = 5 + 4 = 4 + 3 + 2

아이디어

자연수 N을 연속된 자연수 두 개의 합으로 나타낼 경우 N = ((N - 1) / 2) + ((N - 1) / 2 + 1)로 자연수 값이 정해진다. 연속된 자연수 세 개의 합으로 나타낼 경우 N = ((N - 3) / 3) + ((N - 3) / 3 + 1) + ((N - 3) / 3 + 2)로 자연수 값이 정해진다. N을 연속된 자연수 k 개의 합으로 나타낼 경우 $N = \sum_{i=0}^{k - 1}((N - \sum_{j=1}^{k - 1}j)\ /\ k \ + \ i)$ 로 자연수 값이 정해진다.

그러므로 자연수 N을 연속된 자연수 k 개의 합으로 나타내려고 할 때 $(N - \sum_{j=1}^{k - 1}j) \ / \ k$ 를 정수로 표현할 수 있으면 자연수 N을 연속된 자연수 k 개의 합으로 나타낼 수 있고, 정수로 표현되지 않으면 자연수 k 개의 합으로 자연수 N을 나타낼 수 없다고 볼 수 있다.

따라서 k = 2부터 $(N - \sum_{j=1}^{k - 1}j) \ / \ k$ 의 값이 1 이상인 동안 k 값을 증가시키면서, N을 k 개 연속된 자연수로 나타낼 수 있는지 확인하면 된다.

풀이

테스트 케이스의 수 T를 입력받고 각 테스트 케이스마다 자연수 N을 입력 받는다.

k 값을 2로 초기화하고, $\sum_{j=1}^{k - 1}j$ 값을 저장하기 위해 remainder를 초기화한다.

k <= N - remainder인 동안 k 값을 증가시키면서 N - remainder가 k로 나누어 떨어지는지 확인한다. (k로 나누어 떨어지면 나눈 값을 정수로 나타낼 수 있다.)

N - remainder가 k로 나누어 떨어지면 N을 k개 연속 자연수로 나타낼 수 있는 것임으로 answer 값을 증가시킨다.

다음 반복에서 $\sum_{j=1}^{k - 1}j$ 값이 현재 k 값만큼 커져야 하므로, remainder값을 k만큼 증가시키고, k 값을 증가시킨다.

코드

#include <iostream>
using namespace std;

int T, N;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> T;
    for (int t = 0; t < T; t++)
    {
        cin >> N;

        int answer = 0;
        int k = 2;
        int remainder = 1;
        while (k <= N - remainder)
        {
            if ((N - remainder) % k == 0)
                answer++;

            remainder += k;
            k += 1;
        }
        cout << answer << '\n';
    }
    return 0;
}

결과