[C/C++] 백준 #1789 수열의 합(수학)

서로 다른 수들로 이루어진 수열의 합을 원하는 값으로 맞추는 방법은 아주 다양하게 있을겁니다.  그런데, 참여하는 수의 갯수를 최대한으로 하기 위해서는 참여하는 수가 작을 수록 좋겠죠.

 

이 문제를 풀기 위해서는 바로 이 방법을 사용했습니다.

 

\[ N(N+1)/2 \le S \]

위의 식을 만족하는 최대의 N을 구하면 되겠죠.  근의 공식을 이용하면 쉽게 N의 범위를 구할 수 있습니다.

 

\[ N \le \frac{1 + \sqrt{1+8S}}{2} \]

 

오른쪽항은 정수일수도 아닐 수도 있지만, N은 정수여야 하므로, 오른쪽항의 값의 정수값을 구하면 됩니다.

 

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

//---------------------------------------------------------
//    baekjoon #1789
//        - by Aubrey Choi
//        - created at 2019-06-14
//---------------------------------------------------------
#include <stdio.h>
#include <math.h>

//    n*(n+1)/2 < S --> n^2 + n - 2S < 0
//    n < (-1 + sqrt(1 + 8S))/2
int main()
{
    long long S;
    scanf("%lld", &S);
    printf("%d\n", (int)((-1.0 + sqrt(1.0 + 8.0*S)) / 2.0));
    return 0;
}

 

Sigma notation