[BOJ] 백준 1011번: Fly me to the Alpha Centauri

https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

x 지점에서 출발하여 y 지점으로 가는데 이전에 k번 건너뛰었다면 다음번엔 k-1번 k번 k+1 번 건너 뛸 수 있을때 x에서 y로 가는데 최소 점프수를 구하는 문제입니다. 다만 마지막 y 지점에 도착할 땐 반드시 1번 뛰어야 합니다.

만약 내가 x에서 y로 갈때 최소 점프수로 가고 싶다면 점프할때 k를 1씩 늘리거나 유지하다가 어느 시점에서 부터 k를 1씩 감소하시키면서 y에 도착하는 것이 가장 베스트일겁니다.

즉 1 2 3 2 1 과 같은 꼴이 될겁니다. 

1 2 3 2 1 는 1+2, 2+1, 3으로 3의 제곱인 9만큼의 거리에서 최적으로 점프하는 경우입니다.

만약 1 2 3 4 3 2 1 로 점프를 하는 경우는 1+3 , 2+2 , 3+1, 4 로 4의 제곱인 16만큼의 거리에서 최적으로 뛸 수 있습니다.

이로써 우리는 x와 y의 거리가 특정 자연수 n에 대한 제곱인 경우 최적의 점프 횟수가 2*n -1 인것을 알았습니다.

그럼 가야하는 거리가 (n-1)*(n-1) 과 n*n 사이의 거리의 최적의 점프횟수는 어떻게 구할까요

만약 가야하는 거리가 12인 경우를 구해봅시다. sqrt(12)는 3.xx로 3이라고 보면 아마도 9의 최적 횟수 + 1 이상과 16의 최적 점프 횟수 이하의 어느 한 수 일겁니다. 

16인 경우부터 거꾸로 가면서 확인해보겠습니다. 

거리 16 : 1 2 3 4 3 2 1 (6)

거리 15 : 1 2 3 3 3 2 1 (6)

거리 14 : 1 2 3 3 2 2 1 (6)

거리 13 : 1 2 3 3 2 1 1 (6)

거리 12 : 1 2 3 3 2 1  (5)

횟수를 줄이기 위해서 k는 앞 뒤 점프 횟수와 k-1 k k+1 사이를 유지해야하므로 가장 큰 점프 횟수를 줄여야합니다.

즉, 거리가 16인 경우에 최적 점프 횟수를 줄이려면 적어도 sqrt(16) = 4 의 거리가 줄어야 합니다.

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef double d;
typedef pair<d, d> pdd;
typedef pair<int,int> pii;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int t;
	cin >> t;
	for (; t--;) {
		int x, y ,ans =0;
		cin >> x >> y;
		int n = y - x;
		int r = sqrt(n);
		if(r*r == n){
			ans = r * 2 - 1;
		}
		else {
			ans = 2 * (r + 1) - 1;
			int dif = (r + 1) * (r + 1) - n;
			if (dif >= r + 1) {
				ans -= 1;
			}
		}
		cout << ans <<"\n";
	}
}