[BOJ] 1024 - 수열의 합

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

BOJ - 수열의 합

문제 유형: 수학, 그리디

문제 난이도: Silver II

시간 제한: 2초

메모리 제한: 128MB

 

문제

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

 

입력

첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.

 

출력

만약 리스트의 길이가 100보다 작거나 같으면, 연속된 수를 첫째 줄에 공백으로 구분하여 출력한다. 만약 길이가 100보다 크거나 그러한 수열이 없을 때는 -1을 출력한다.

 

풀이

 

l개의 길이의 가장 작은 수를 x라 하자.

x부터 순차적으로 l개의 합은

x + (x+1) + ... (x+l-1) = N의 관계가 성립한다.

x * l = N - l(l-1)/2이다.

N-l(l-1)/2가 0이상이고, (N-l(l-1)/2)/l이 정수라면, 만들 수 있다는 뜻이다.

유효하면 x = (N-l(l-1)/2)/l부터 순차적으로 l개의 수를 출력해주면 된다.

l을 100까지 늘려서 시도해보고 가능한대로 출력해주고, 100까지 시도하고도 실패시 -1을 반환한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n, l;

int main(int argc, char *argv[]) {
  cin >> n >> l;

  while (l <= 100) {
    int y = l * (l - 1) / 2;
    if (n >= y && (n - y) % l == 0) {
      int x = (n - y) / l;
      for (int i = 0; i < l; ++i) {
        cout << x + i << " ";
      }
      cout << "\n";
      return 0;
    }
    l++;
  }

  cout << "-1\n";

  return 0;
}