[C++] 백준 1024 수열의 합

https://www.acmicpc.net/problem/1024
제목 : 수열의 합
solved.ac 난이도 : Silver II

처음엔 투 포인터로 풀려고 했다. 근데 짜고나서 경과 시간을 재보니 시간초과가 날 만한 경과 시간이었다. 그래서 찾아 본 결과 수열의 합을 구하는 공식을 활용하면 시간을 더 빨리 당길 수 있었다는 것을 알게 되었다.

풀이

우리는 수열의 합이 N인 시작항과 끝항을 구할 수 있고 첫항과 끝항을 이용한 특정 길이의 수열의 합을 구할 수 있다.
수열은 음수가 아닌 정수로 이루어진 수열이라고 했기 때문에 수열의 첫 항은 무조건 0이다.
이걸 활용해 우리는 방정식을 세울 수 있다.

수열의 합 : N, 필요한 수열의 길이 : L, 차수 : 1
시작항 : 0 + (n - 1) * 1 = n - 1
끝항 : 0 + ( (n - 1) + (L - 1) ) * 1 = n + L - 2
시작항과 끝항을 포함한 길이 L 의 수열의 합 :
L * ( (n - 1) + (n + L - 2) ) / 2 = N
2n + L - 3 = 2N / L
2n = 2N / L - L + 3

이렇게 세운 방정식의 N 과 L 자리에 우리가 입력받은 수를 집어 넣으면 된다.
위 식을 바탕으로 2줄부터 100줄까지 계산을 하고, 조건에 맞으면 바로 반복문을 빠져 나오는 식으로 구했다.
소수가 나오지 않게 하기 위해서 나머지 연산을 중간에 조건으로 주었고, 시작항이 음수면 -1을 출력하게 만들었다. 그리고 수열의 길이가 101이상인 수열도 -1을 출력하게 했다.

#include <iostream>

using namespace std;

int main()
{
    long long N, L;
    cin >> N >> L;
    long long first = - 1, end = - 1;
    for (int i = L; i <= 100; i++) {
        if ((2 * N) % i == 0) {
            long long term = (2 * N / i) - i + 3;
            if (term % 2 == 0) {
                first = (term / 2) - 1;
                end = (term / 2) + i - 2;
                break;
            }
        }
    }
    if (first < 0) cout << -1;
    else {
        for (int i = first; i <= end; i++) {
            cout << i << " ";
        }
    }
}