[백준] 1024 :: 수열의 합

 

https://www.acmicpc.net/problem/1024

1024번: 수열의 합

 

완전 수학수학 스러운 문제이다. 

 

문제를 요약하자면 연속된 l개의 수를 합해 n을 만들 수 있는 수열을 찾으면 된다. 

이때 연속된 l개의 수는 l개 부터 최대 100개 까지일 수 있다.

 

우리는 여기서 힌트를 얻어야 한다. 100개정도는 탐색해 볼 수 있다는 힌트

 

"연속된 수"라는 힌트가 있기 때문에 우리는 연속된 수의 시작수 (a 라고 하겠다)만 찾으면 된다.

 

만약 a부터 연속된 l개의 수의 합을 구한다고 가정하자

 

a  a+1 a+2 ..... a+(l-1) 까지가 수열이 될 것이다

 

우리는 이 수열의 합을 구해야 한다.

방법은 1~ a+(l-1) 까지의 수열의 합에서 1~(a-1)까지의 수열의 합을 빼는 것이다.

 

1부터 n까지 연속된 수의 합을 구하는 공식인 n(n+1)/2를 이용해 계산을 하면 된다.

 

이를 통해 우리는 시작수 a를 구할 수 있고 , 이를 수식으로 풀어 코드화 하면 된다. 

계산해 보면,

x개의 연속된 수에 대해 시작 수 a는 (2*n - x*x + x) / (2*x) 가 된다. 이 때 a는 정수여야 하며, 동시에 음수이면 안된다.

 

소스코드

https://github.com/kumakuma34/Algorithm/blob/master/BOJ/1024%5B%EC%88%98%EC%97%B4%EC%9D%98%20%ED%95%A9%5D.cpp

/*
BOJ 1024[수열의 합]
*/
#include <iostream>
using namespace std;
 
int n, l;
int main() {
    cin >> n >> l;
    int ans = -1;
    int x = l;
    for (; x <= 100; x++) {
        if( (2 * n - x * x + x) % (2 * x) ==0 && (2 * n - x * x + x) >=0)
            ans = (2 * n - x * x + x) / (2 * x);
        if (ans != -1) break;
    }
    if (ans != -1) {
        for (int i = 0; i < x; i++) {
            cout << ans << " ";
            ans++;
        }
    }
    else
        cout << ans << endl;
 
}