[백준] 1011번 Fly me to the Alpha Centauri
거리에 따라 생기는 규칙을 파악하면 풀기 쉬운 문제입니다.
3 = 1, 1, 1
4 = 1, 2 ,1
5 = 1, 2, 1, 1
6 = 1, 2, 2, 1
7 = 1, 2, 2, 1, 1
8 = 1, 2, 2, 2, 1
9 = 1, 2, 3, 2, 1
과 같은 규칙을 가지고 있음으로 제곱수의 경우 sqrt(n) - 1, 다음 제곱 수까지의 수 절반 이하의 경우 sqrt(n), 절반 이후의 경우에는 sqrt(n) + 1을 가지고 있는 것을 볼 수 있습니다.
위와 같은 규칙을 이용해 아래와 같이 풀면 됩니다.
#include <iostream>
#include <cmath>
using namespace std;
int main() {
long long int n, start, end, count = 0, sum = 0;
double count1 = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> start >> end;
sum = end - start;
count = sqrt(double(sum));
count1 = sqrt(double(sum));
if (sum == 3 || sum == 2 || sum == 1) {
cout << sum << "\n";
}
else if (count1 == count) {
cout << 2 * count - 1 << "\n";
}
else if (count1 >= double(count) + 0.5) {
cout << 2 * count + 1 << "\n";
}
else {
cout << 2 * count << "\n";
}
}
}