[BOJ-1011]Fly me to the Alpha Centauri

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

[접근방법]

수학

DFS로 접근을 한 후 시간초과를 받고나서 생각을 해봤는데

방문해서 검색해야하는 종류가 대략 2^31-1 이라서 DP도 안되고 ... 

그래서 이럴 경우에는 수학식으로 풀이해야한다는 것을 알았다.....

dist : 가야하는 거리.

N : 이동 1회에 가장 먼거리를 갔을 때 거리 값.

2N-1 : 최적의 이동을 했을 때 갈 수 있는 값.

ceil( (dist-N^2)/N ) : 최적의 이동거리를 간 후, 진행해야하는 횟수.

이를 이용하여 구하면 된다.

[C++11 source Code]

#include<cstdio>
#include<cmath>
typedef long long ll;
int main() {
    int tc;
    for (scanf("%d", &tc); tc > 0; tc--) {
        ll x1, x2;
        scanf("%lld%lld", &x1, &x2);
        ll dist = x2 - x1;
        for (ll i = 1; i < 50000; i++) {
            ll n2 = i*i;
            ll rem = ceil((dist - n2) / (float)i);
            ll mn = 2 * i - 1;
 
            if (n2 <= dist && dist < (i+1)*(i+1) ) {
                printf("%lld\n", mn + rem);
                break;
            }
        }
    }
    return 0;
}