[BOJ 1011번] (Math) Fly me to the Alpha Centauri (C++)

Fly me to the Alpha Centauri (Gold 5)

문제

전체 문제 보기

1011번: Fly me to the Alpha Centauri

접근법

이 문제는 정답의 규칙을 발견하면 간단한 수학 연산 몇 가지로 정답을 구할 수 있다. 규칙을 찾기 위해서 아래의 표를 살펴보자.

▲ 출발지점으로 부터 거리에 따른 최소 이동 횟수를 계산한 표

이 표를 살펴보면 두 가지 규칙을 찾을 수 있다.

• 항상 거리가 1,4,9,16 제곱수 이후 에서 이동 횟수가 1 증가하는 규칙을 볼 수 있다.
• 제곱수에서 증가한 후, 4 에서는 2회, 9 이후에는 3회, 16 이후에는 4회 이후에 이동 횟수가 1씩 증가하는 규칙을 살펴 볼 수 있다. 즉 제곱수의 제곱근sqrt(dist-1)회 이후부터는 1 증가한다.

이 두가지 규칙을 코드로 계산하여 출력하면 결과를 얻을 수 있다.

구현

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);


    size_t T;  // 입력 받을 문자열 개수
    cin >> T;
    while (T--)
    {
        int x, y;
        cin >> x >> y;
        const int dist = y - x;

        int sqrtDist = static_cast<int>(sqrt(dist-1));
        if (dist - sqrtDist * sqrtDist <= sqrtDist)
        {
            cout << 2 * sqrtDist << endl;
        }
        else
        {
            cout << 2 * sqrtDist + 1 << endl;
        }
    }

    return 0;
}