[C++] 백준/Silver/1024. 수열의 합

수열의 합 (백준 1024번)

문제 개요

• 문제 설명:
  주어진 자연수 N 과 최소 길이  L이 있을 때, 연속된 자연수들의 합이  N이 되는 수열을 찾는 문제다.
• 조건:
  • 수열의 길이는 최소  L이상이어야 하며, 길이가 100을 초과할 수 없다.
  • 수열에 포함된 수는 음수가 될 수 없다.
  • 만약 조건을 만족하는 수열을 찾지 못하면 "-1"을 출력한다.

---

접근 방법

문제를 효율적으로 해결하기 위해 수학적 접근법을 사용한다.
연속된 $\text{len}$개의 자연수의 합을 수식으로 표현하면 다음과 같다.

1. 연속된 수열의 합 공식

연속된 $\text{len} $개의 정수 $ x, x+1, x+2, \dots, x+\text{len}-1 $의 합은:
$$
\text{Sum} = \text{len} \times x + \frac{\text{len} \times (\text{len} - 1)}{2}
$$
여기서 $x $는 수열의 시작 값이다.

문제에서 우리가 구해야 하는 조건은 이 합이 $ N $과 같아야 한다.
$$
\text{len} \times x + \frac{\text{len} \times (\text{len} - 1)}{2} = N
$$
따라서, $x$는 다음과 같이 구할 수 있다.
$$
x = \frac{N - \frac{\text{len} \times (\text{len} - 1)}{2}}{\text{len}}
$$
여기서 주의할 점은:

• $x$가 정수여야 한다.
• $ x $는 음수가 될 수 없다.

2. 알고리즘 전략

• 길이 선택:
  $ \text{len} $를 최소 $ L $부터 최대 100까지 순회하며,
  각 길이에 대해 위 식으로 $ x $를 구한다.
• 조건 확인:
  • $ N $보다 $ \frac{\text{len} \times (\text{len} - 1)}{2} $가 크다면,
    $ x $가 음수가 될 수 있으므로 더 이상 진행할 필요가 없다.
  • $ (N - \text{temp}) $가 $ \text{len} $로 나누어 떨어져 정수 $ x $를 얻을 수 있어야 한다.
• 출력:
  조건을 만족하는 경우, 길이 $ \text{len} $만큼 $ x, x+1, \dots, x+\text{len}-1 $을 출력하고 프로그램 종료.
  만약 모든 경우를 시도한 후에도 조건에 맞는 수열을 찾지 못하면, "-1"을 출력한다.

코드 설명

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);

    long long N; // 목표 합
    int L;        // 최소 수열 길이
    cin >> N >> L;

    // len: 수열의 길이를 L부터 100까지 시도
    for (int len = L; len <= 100; ++len)
    {
        // 수열의 합에서, x가 0부터 시작했을 때 얻을 수 있는 추가 누적합
        // 즉, 0, 1, 2, ..., (len-1)의 합 = len * (len-1)/2
        long long temp = (long long)len * (len - 1) / 2;

        // 만약 N이 이미 이 누적합보다 작다면, 더 이상 탐색할 필요 없으므로 break
        if (N < temp) break;

        // (N - temp)이 len으로 나누어 떨어지면, x가 정수로 계산됨
        if ((N - temp) % len != 0) continue;

        // 시작 수 x 계산
        long long x = (N - temp) / len;
        if (x < 0) continue;

        // 조건을 만족하는 경우, x부터 시작하는 len개의 수를 출력
        for (int i = 0; i < len; ++i)
        {
            cout << (x + i) << " ";
        }
        cout << "\n";
        return 0;
    }

    // 모든 경우를 시도해도 조건에 맞는 수열을 찾지 못한 경우 -1 출력
    cout << "-1\n";
}