[백준OJ] 1789번 수들의 합

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

1789번: 수들의 합

---

 

-풀이-

서로다른 자연수들의 합이 S일때 , 서로다른 자연수의 개수N의 최댓값을 구하는 문제이다.

최댓값을 구하기위해서 1부터 하나 하나 더해서 S를 넘지않는 최댓값을 구한다.

ex) 200을 넘지않는 최댓값은 1~19 까지 더한값인 190이 된다. 

그럼 위에 구한 마지막 더한값 (위에서 구한 19) 가 답이된다.

왜 19개가 답인가? 답은 간단하다. 1~19까지 더해주면 190이 된다. 남은 10을 마지막숫자(19)에 더해주어 1~18까지 더한뒤, 29를 더해주면 깔끔하게 답이 나온다.

 

-시간복잡도-

등비수열의 공식에 따라서, 최대 1~82억까지 반복해야 하므로, 상수시간인 O(sqrt(s)) 가 된다.

 

-코드-

#include <iostream>
#include<algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	long long s;
	cin >> s;
	int cnt = 0;
	for (int i = 1; s - i >= 0; i++) {
		s -= i;
		cnt++;
	}
	cout << cnt;
	return 0;
}