백준2018 수들의 합 5

작성일 | In

문제 링크

  • http://icpc.me/2018

사용 알고리즘

  • Parametric-Search

시간복잡도

  • (sqrtN * logN)

풀이

이 문제와 비슷하지만, 길이의 상한이 없습니다. 상한을 직접 구해야 합니다.

연속된 자연수 몇 개를 더해서 N을 만들 때 자연수의 개수를 최대화 시키려면 1부터 시작해야 한다는 것을 쉽게 알 수 있습니다.
길이를 x라고 하면 x(n+1)/2 = N이기 때문에 x는 O(sqrtN)입니다.

문제에서 N은 최대 1000만이므로, 안전하게 10000까지 보면 시간 내에 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

typedef long long ll;
ll n, l;
int ans;

ll sum(ll s){
	return s * (s + 1) / 2;
}

ll sum(ll start, ll len){
	return sum(start + len - 1) - sum(start - 1);
}

void chk(ll len){
	ll l = 1, r = 1e9 + 7;
	while (l <= r){
		ll m = l + r >> 1;
		ll x = sum(m, len);
		if (x == n){
			ans++; return;
		}
		if (x > n) r = m - 1;
		else l = m + 1;
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 2; i <= 10000; i++) chk(i);
	ans++;
	cout << ans;
}