C++:: boj 1011 <Fly me to the Alpha Centauri>

점화식을 잘 만들면 되는 문제이다. 이때 주의해야 할점은 어느 순간에 2^31 승을 넘어가는지 체크해서 범위를 지정해주어야 한다는 점이다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
/*
0 1 2 3 3 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 8
idx: 0 1 2 3 4 5  6  7  8  9 10
res: 0 1 2 4 6 9 12 16 20 25 30 ....
*/
int main() {
	int t, x, y;
	vector<long long> dp(92682, 0);
	for (int i=1; i<92681; i++) {
		if (i%2) dp[i] = 1LL*(i+1)*(i+1)/4;
		else dp[i] = dp[i-1] + (i+1)/2;
	}
	dp.back() = INT32_MAX;
	cin >> t;
	while (t--) {
		cin >> x >> y;
		y -= x+1;
		cout << upper_bound(dp.begin(), dp.end(), y) - dp.begin() << "\n";
	}
}