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

- 링크: www.acmicpc.net/problem/1024

 

이런 문제가 제일 어렵습니다. 단순한 것 같으면서? 막상 풀려고 하면 손이 움직이지 않습니다. 왜냐, 저는 수알못이기 때문입니다.

N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오.

이떄 입력조건이 N=[1, 10억], L=[2, 100]인 점 유의하셔야 합니다. "음이 아닌 정수 리스트"를 구한다는 것도 주의를 하시고요. 즉 수가 0 이상이라는 거겠죠

N의 범위가 넓기 때문에 브루트포스나 뭐 여타 등등의 방법은 안됩니다. 결국 정공법인 수학으로 풀어야 합니다

 

적당히 수열의 맨 처음 수를 a 라고 하겠습니다.

(L=2) a, a+1 -> 합: 2a+1
(L=3) a, a+1, a+2 -> 합: 3a+3
(L=4) a, a+1, a+2, a+3 -> 합: 4a+6
...
(L=n) a, a+1, ... a+n -> 합: n*a + (n*(n-1))/2

그때 순열의 길이(L)에 따른 합을 쓰면 이렇게 됩니다. 결국 저 목록중에 a에다 적당한 값을 넣었을 때 합이 N이 되도록 할 수 있느냐? 이걸 찾으면 순열을 만들 수 있겠죠

처음엔 이상한 가정(L%2 != N%2)을 세우고 풀기 시작해서 헛다리를 좀 짚었습니다.

그 다음엔 for 루프 인덱스 범위에 eq가 빠져서 삽질을 약간 했습니다.

맥에서 C++ 개발환경 테스트겸 문제 아무거나 하나 쉬운거 풀어보려고 한건데, 한시간을 써버렸네요 ;

#ifdef ONLINE_JUDGE
    #include <bits/stdc++.h>
#else
    #include "stdc++.h"
#endif  // ONLINE_JUDGE

using namespace std;


int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, L;
    cin >> N >> L;

    for (int i=L; i<=100; ++i) {
        int remainder = (i*(i-1))/2;
        int unit = N-remainder;

        if (unit>=0 && unit%i==0) {
            int a = unit / i;
            for (int j=0; j<i; ++j) {
                cout << a+j;

                if (j != i-1)
                    cout << " ";
            }
            return 0;
        }
    }
    cout << "-1\n";

    return 0;
}