백준 1011번 Fly me to the Alpha Centauri C++

문제 링크 : https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

문제 풀이

 이 문제는 초기 위치에서 시작해, 이전 변위와 현재 변위의 차가 1 이하가 되도록 이동하여, 마지막 위치까지 이동했을 때 이동 횟수의 최솟값을 묻는 문제이다.

 i번째 이동에서의 이동거리를 D(i)로 정의해보자. 이제 각각의 이동에 대해 D(i)를 최대로 할 수 있게 Greedy방법을 써보자. 

현재 위치 current에 대해 D(i)로 이동하려면

         (a) 남아있는 거리 d는 적어도 1 + 2 + ... + D[i]-1보다는 커야한다.

조건 (a) 를 만족해야함이 자명하다(변위는 1씩 감소할 수 있는데 마지막에 변위가 1로 끝나야하므로) . 또, D(i)는 이전 변위 D(i-1)에 의해서 결정되는데, 둘의 차이는 항상 1보다 작거나 같다. 따라서 d의 범위에 따라 D(i-1)을 이용해서 D(i)를 정해주면 나머지도 귀납적으로 정의가 될 것이다.

Case 1) | current와 y의 거리 | = d + D(i) ≥ 1 + 2 + .. + D(i-1) +  (D(i-1) + 1)
 D(i) = D(i-1) + 1이 되어도 조건 (a) 를 만족하므로 D(i) = D(i-1) + 1가 되는 것이 가장 유리하다.

Case 2)|current와 y의 거리| = d + D(i) ≥ 1 + 2 + .. + D(i-1)
 D(i) = D(i-1) + 1인 경우는 조건 (a) 를 만족하지 않고 D(i) = D(i-1)까지만 조건을 만족하므로 D(i) = D(i-1)인 경우가 가장 유리하다.

Case 3) elsewise
D(i)는 D(i-1) - 1이 될 수 밖에 없다.

 

 

코드

#include <iostream>
using namespace std;

int main()
{
    int T,x0,y0;
    cin>>T;
    while(T--)
    {
        cin>>x0>>y0;
        int delta=0,current=x0,sum=1,n=0;
        
        while(current != y0)
        {
            n++;
            if(y0-current>=sum)
            {
                delta ++;
                current += delta;
                sum += delta + 1;
            }
            else if(y0-current >= sum - delta-1)
            {
                current += delta;
            }
            else
            {
                sum -= delta + 1;
                delta --;
                current += delta;
            }
        }
        cout<<n<<"\n";
    }
}

y0 - current = |current와y의 거리|

n = |이동 횟수|

delta = D(i)

x0 = |초기위치|, y0 = |목표 위치|

T = |테스트 케이스|