백준 문제 1011번 Fly me to the Alpha Centauri 문제풀이 c++

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

1011번: Fly me to the Alpha Centauri

문제 해석

시작위치 x에서 도착 위치 y까지 문제에서 제시한 규칙에 따라 이동하는 최소 작동 횟수를 구하는것이 문제인데

결론 부터 말하자면 그리디한 방법으로 이동거리를 증가 시키면서 최고점을 딱 찍고

다시 감소 시키면 그것이 최소 횟수가 된다.

한 0부터 16정도까지 종이에 쓰다보면 규칙을 찾을수있다.

1=1

1+1=2

1+2+1=4

1+2+2+1=6

1+2+3+2+1=9

1+2+3+3+2+1=12

1+2+3+4+3+2+1=16

1+2+3+4+4+3+2+1=20

1+2+3+4+5+4+3+2+1=25

....

이런식이다.

즉 d=y-x라고하면

0<d<=1 일때 답 1

1<d<=2 일때 답 2

2<d<=4 일때 답 3

4<d<=6 일때 답 4

6<d<=9 일때 답 5

9<d<=12 일때 답 6

12<d<=16 일때 답 7

......

그것을 코드로 나타내면 아래와같다 √2^31이 대략 46341 정도이므로 넉넉하게 47000번정도 안에 찾을 수 있다.

 

 

 

코드

#include <iostream>
using namespace std;
typedef long long int ll;
ll solve(ll n);
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int x,y,t;
    cin>>t;
    while(t>0)
    {
        cin>>x>>y;
        cout<<solve(y-x)<<"\n";
        t--;
    }
}
ll solve(ll n){
    for(ll i=1; i<=47000; i++)
    {
        ll a=i*(i-1);
        ll b=i*i;
        ll c=(i+1)*i;
        if(a<n&&n<=b)
        {
            return i*2-1;
        }
        else if(b<n&&n<=c)
        {
            return i*2;
        }
    }
}