백준 #1024 수열의 합

수열의 합은 수열이 어떻게 이루어졌느냐에 따라서 계산됩니다.  대표적으로 등차수열과 등비수열은 공식에 의해서 구할 수 있습니다.  이 문제는 연속된 수열의 합을 구하는 것이기 때문에 등차수열의 합을 이용하면 됩니다.

 

문제는 다음과 같습니다.

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

1024번: 수열의 합

 

이 문제는 길이가 짝수일 때와 홀수일 때의 합이 서로 다릅니다.  초기항 s이고 길이가 n인 수열의 합은 다음과 같이 나타낼 수 있습니다.

 

\[ s + (s+1) + ... + (s+(n-1)) = \frac{n(2s+n-1)}{2} \]

 

만약 n이 홀수라면, \(2s+n-1\) 의 값은 짝수가 됩니다.  \(\frac{2s+n-1}{2}\)는 이 수열의 평균입니다.  평균값은 자연수가 됩니다.  만약 평균값이 존재하지 않는다면, 우리는 길이가 n인 수열을 얻을 수 없습니다.

 

비슷하게 n이 짝수라면, \(2s+n-1\) 의 값은 홀수가 되고, 평균값은 자연수가 되지 않지만, 나머지는 n/2 가 됩니다.  만약 평균을 구하는데 있어서 나머지가 n/2이 아니라면 길이가 n인 수열을 얻을 수 없습니다.

 

이를 이용해서 문제를 풀었습니다.  조금 더 개선된 알고리즘을 만들 수도 있을 것 같은데, 그럴려면 길이 n을 소인수분해해야 하는데, 그다지 좋은 개념은 아닐 듯 합니다.  소인수분해후 매칭하는 것도 귀찮고요.  그래서 이런식의 알고리즘내에서는 꽤 무식하게 짰습니다.

 

다음은 제가 짠 소스입니다.  소스는 참고용으로만 봐주세요.

//----------------------------------------------------------------------------------------
//  baekjoon #1024 - Sum of Number Sequences.
//    - by Aubrey Choi
//    - created at 2019-07-03
//----------------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
  int n, s;
  scanf("%d%d", &n, &s);
  for(; s*(s-1) <= 2*n && s <= 100; s++)
  {
    if((s & 1) && (n%s == 0))
    {
      for(int i = n/s-s / 2; i <= n/s+s / 2; i++)
        printf("%d ", i);
      putchar('\n');
      break;
    }
    if(!(s & 1) && (n % s == s/2))
    {
      for(int i = n/s - s/2 + 1; i <= n/s + s/2; i++)
        printf("%d ", i);
      putchar('\n');
      break;
    }
  }
  if(s*(s - 1) > 2 * n || s > 100) puts("-1");
  return 0;
}