[C/C++] 백준 - 1789번 : 수들의 합

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

1789번: 수들의 합

문제

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

 

간단한 수학 문제이다.

 

단, 주의해야할 점이 S보다 작은 수가 아닌 S와 같은 값이 나와도 된다.

딱 보고 떠올라야하는 공식은 1부터 N까지 모두 더한 값이 

-> N * (N + 1) / 2

 

이걸 먼저 떠올려야한다. 그래서 주어진 S에 2를 곱한 후 그것의 제곱근을 먼저 파악한다. 

그리고 그 제곱근을 위 공식에 대입해 계산한 값이 S보다 크면 이보다 1 작은 값이 정답이 될 수 밖에 없다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000007
#define endl '\n'

using namespace std;

void solution() {
	ll S;
	cin >> S;
	ll x = sqrt(S*2);
	if ((x * (x + 1)) / 2 > S) x -= 1;
	cout << x << endl;
}

int main() {
	fastio;
	solution();

	return 0;
}