문제풀이/백준oj
[백준OJ] 1789번 수들의 합
Hyeon-Uk
2021. 7. 2. 00:46
반응형
https://www.acmicpc.net/problem/1789
1789번: 수들의 합
첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.
www.acmicpc.net
-풀이-
서로다른 자연수들의 합이 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;
}
반응형