[백준 1011번] Fly me to the Alpha Centauri (C++)

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int T;

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> T;
    while(T--)
    {
        ll x, y;
        cin >> x >> y;

        ll gap = y-x;
        double n = sqrt(gap);
        int n2 = round(sqrt(gap));

        if(n <= n2) cout << 2*n2-1 << "\n";
        else cout << 2*n2 << "\n";
    }

    return 0;
}

 

먼저 거리에 따른 규칙을 찾아봐야 한다.

거리 형태 횟수
1        1 1
2       11 2
3      111 3
4      121 3
5     1211 4
6     1221 4
7    12211 5
8    12221 5
9    12321 5
10  123211 6
11  123221 6
12  123321 6
13 1233211 7
14 1233221 7
15 1233321 7
16 1234321 7

 

보면 처음 1, 2 이후로는 4, 9, 16과 같이 제곱이 되는 수를 기점으로 이후 횟수가 증가된다.

거리를 전부 제곱근을 취해보면 아래와 같다.

1 = 1.0
2 ≈ 1.414 //반올림 1
3 ≈ 1.732 //반올림 2
4 = 2.0 
5 ≈ 2.236 //반올림 2
6 ≈ 2.449 //반올림 2
7 ≈ 2.646 //반올림 3
8 ≈ 2.828 //반올림 3
9 = 3.0
10 ≈ 3.162 //반올림 3
11 ≈ 3.317 //반올림 3
12 ≈ 3.464 //반올림 3
13 ≈ 3.606 //반올림 4
14 ≈ 3.742 //반올림 4
15 ≈ 3.873 //반올림 4
16 = 4.0

 

반올림한 값을 참고하여 다시 횟수를 살펴보자.

제곱이 되는 수를 기점으로 해당 수 포함하여 그전까지는 2*반올림 수 -1, 그 이후는 2*반올림 수 인 것을 볼 수 있다.

이를 식으로 세워보자 반올림 수는 n으로 가정한다.

n이 같은 값들을 보면, 제곱근 수가 n보다 작거나 같을 때 2*n-1이고 제곱근 수가 n보다 크면 2*n인 것을 알 수 있다.

따라서 제곱근 수에 대한 변수와, 제곱근 수를 반올림한 변수 2가지가 필요한 것 또한 알 수 있다.

ex
3 ≈ 1.732 //반올림 2
4 = 2.0 
5 ≈ 2.236 //반올림 2
6 ≈ 2.449 //반올림 2

1.732, 2.0 <= 2 -> 2*n-1 = 3
2.236, 2.449 > 2 -> 2*n = 4

 

따라서 먼저 입력 받은 y, x 를 통해 거리를 구해주고,

거리에 대한 제곱근 값과 제곱근을 반올림한 값을 위에서 계산한 식을 통해 출력해주면 된다.

해당 규칙은 바로 찾지 못해 거리에 대한 표를 그려보고, 인터넷 검색을 참고하여 찾을 수 있었다.