[BOJ_C++] 1024번 : 수열의 합

참고한 블로그 : https://hooongs.tistory.com/334

1. 문제

2. 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>

using namespace std;

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

    bool result = false;
    long n; int l, x; cin >> n >> l;
    for (int i = l; i < 101; i++) {
        x = n - (i * (i + 1) / 2); //사실상 이 곳의 x는 LX라고 생각하여도 무방함.
        if (x % i == 0) {
            x = x / i;
            if (x >= -1) {
                for (int j = 1; j < i + 1; j++)
                    printf("%d ", x + j);
                result = true;
                break;
            }
        }
    }
    if (!result) printf("-1");

    return 0;
}

• 연속된 L개의 숫자들로 더해진 합은 아래 수식으로 표현할 수 있다.

N = (x+1) + (x+2) + ... + (x + L)
Lx = N - L * (L+1) / 2

• 다음과 같은 수식으로 보아 L로 N - L * (L+1) /2를 나누었을 때 나누어 떨어진다면, x가 정수가 된다. 즉, 정수 리스트를 구할 가능성이 생기게 된다.
• 이때 음이 아닌 정수 리스트가 되어야 하기 때문에 x+1의 값이 0보다 크거나 같은지 확인해야 한다.
• 정수 리스트를 출력했다면 더이상 for문을 실행할 이유가 없기 때문에 result에 true를 넣고 for문을 종료한다.
• for문이 종료된 뒤 result의 값이 false라면 "-1"을 출력하고 프로그램을 종료한다.

3. 결과