수열의 합 C++ - 백준 1024

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

수학 문제.

문제 접근

연속된 수열이므로 이는 $d=1$인 등차수열이다.

따라서 등차수열의 합 공식을 사용하면 쉽게 풀 수 있는 문제이다.

$d=1$인 등차수열의 합 공식 중 초항이 $a$ 길이가 $l$인 경우

$(a\cdot 2+l-1)\cdot l/2$로 구할 수 있다.

길이가 $l$일때 초항을 증가시키면서 합의 크기를 늘려간다.

이때 $n$을 넘어가게 되면 불가능한 경우이므로 초항의 크기를 조정하고,

길이를 늘린다.

$n$의 범위가 10억이기 때문에 시작을 0부터 하면 TLE가 난다.

따라서 시작점을 길이가 $l$인 최적해의 시작점-3 (소수점 보정)

으로 두어 TLE를 해결했다.

코드는 다음과 같다.

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

int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll n,l; cin >> n >> l;
    ll a=0;
    if(n/l-l/2>3) a=n/l-l/2-3; 
    long long sum=(a*2+l-1)*l/2;
    while(sum!=n && l<=100){
        if(sum>n){
            l++;
            if(n/l-l/2>3) a=n/l-l/2-3;
            else a=0;
        }
        else a++;
        sum=(a*2+l-1)*l/2;
    }
    if(sum!=n){cout << -1;return 0;}
    for(int i=0;i<l;i++) cout << a+i << ' ';
    return 0;
}