[ 백준 / C++ ] 1011 : Fly me to the Alpha Centauri

[ 문제 ]

 

1011번: Fly me to the Alpha Centauri (acmicpc.net)

 

[ 접근방법 ]

 

밑에 주석을 보면 각 작동 횟수마다 최대 이동 거리를 짝홀에 따라 수식으로 정의할 수 있다.

 

정수에 sqrt(루트)를 씌우면 소수가 나오는데, 이를 다시 정수로 변환하면 소수점 아래가 날라간다.

 

이를 활용하면 작동 횟수를 구할 수 있다.

 

[ 소스코드 ]

 

#include <iostream>
#include <cmath>

using namespace std;

int t;
long long x, y;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    while (t--)
    {
        cin >> x >> y;

        // 1
        // 1 1
        // 1 2 1
        // 1 2 2 1
        // 1 2 3 2 1

        // 1 2 ... n-2 n-1 n-2 ...     2 1     => (n-1)(n-1)
        // 1 2 ... n-2 n-1 n-1 n-2 ... 3 2 1   => (n-1)n
        // 1 2 ... n-2 n-1 n   n-1 ... 4 3 2 1 =>  n^2

        y -= x;
        x = (long long)sqrt(y);
        if (y == x * x)
            cout << 2 * x - 1 << "\n";
        else if (y <= x * (x + 1))
            cout << 2 * x << "\n";
        else
            cout << 2 * x + 1 << "\n";
    }

    return 0;
}