[BOJ] 1011 Fly me to the Alpha Centauri

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

그냥 노가다로 규칙 찾는게 증명하는 것보다 빠르다.

결국은 수열 길이가 있을때 하나씩 증가/감소/유지되는 수열의 길이가 n이 되는 경우가 있느냐... 찾는 문제인데

예를 들어서 수열 길이가 7이라고 하면 1 2 3 4 3 2 1 이런 식으로 이동하는 것이 최대라는 것은 자명하다.

그런데 만약에 이렇게 7번의 이동으로 16의 거리를 이동했으면 그 이하의 거리는 모두 이동할 수 있을까? 당연하다.

항상 수열에서 가장 큰 원소를 하나 줄이면 그 원소는 절대로 다른 원소와 2 이상 차이가 나지 않게 만들수 있는 것을 너무 간단히 증명할 수 있다.

수열  $a_1, a_2, a_3, ... , a_n$  이 있다고 하자.

만약  $a_k$가 최대 원소라고 할 때, $a_{k+1}$랑 $a_{k-1}$는 $a_k$와 같거나 혹은 1 작다.

$a_k$를 하나 줄이면, $a_{k+1}$랑 $a_{k-1}$는 $a_k$와 같거나 혹은 1 크다.

따라서 모든 인접한 원소 사이에 다시 1 초과로 차이나지 않게 된다.

따라서 그냥 위의 거리를 계산해 놓고 거리보다 작은 이동 횟수의 최솟값을 출력하는 문제이다.

설명이 자세하지 않으니까 코드를 보고 이해해 보자.

오버플로우에 유의해야 하고 같은 범위 내에서도 절반으로 쪼개서 이동 횟수를 찾아주는 점을 확인해야 한다.

이동 경로가 홀수냐 짝수냐에 따라서 차이가 좀 나서...

난이도는 1/5정도

#include <cstdio>
 
void func(long long dist)
{
    for(long long t=1;;t++)
    {
        if((t-1)*t<dist && dist<=t*(t+1))
        {
            if(dist<=t*t)
                printf("%lld\n",2*t-1);
            else
                printf("%lld\n",2*t);
            break;
        }
    }
}
 
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        long long t1,t2;
        scanf("%lld %lld",&t1,&t2);
        func(t2-t1);
    }
    return 0;
}