백준1024 수열의 합

작성일 | In

문제 링크

  • http://icpc.me/1024

사용 알고리즘

  • Parametric Search

시간복잡도

  • O((101-L)logN)

풀이

음이 아닌 연속된 정수 x개의 합을 N으로 만들 수 있을지 판단하는 함수 chk(x, N)을 생각해봅시다.
첫 숫자를 s로 한다면 s부터 (s+x-1)까지의 합을 N으로 만들 수 있는지 판단을 해주면 됩니다.
s가 증가하면 합도 증가하기 때문에 파라메트릭 서치로 O(logN)만에 풀 수 있습니다.

L부터 100까지의 모든 자연수 i에 대해 chk(i, N)을 해주면 문제를 O((101-L)logN)만에 풀 수 있습니다.

전체 코드

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
39
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

typedef long long ll;
ll n, l;

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 = 0, r = 1e9 + 7;
	while (l <= r){
		ll m = l + r >> 1;
		ll x = sum(m, len);
		if (x == n){
			for (ll i = m; i < m + len; i++){
				cout << i << " ";
			}
			exit(0);
		}
		if (x > n) r = m - 1;
		else l = m + 1;
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> l;
	for (ll i = l; i <= 100; i++) chk(i);
	cout << -1;
}