BOJ 1011: Fly me to the Alpha Centaur

#BOJ 1011: Fly me to the Alpha Centaur

1011번: Fly me to the Alpha Centauri

#풀이

문제를 읽어보면 마지막에 1광년을 이동한다고 적혀있는데 이 말을 잘 이해해야한다.

 

이 말은 계속 증가된 광년을 넘어오다가 어느 순간이 되면 다시 감소되는 광년을 넘어와야 한다는 뜻이다.

 

나는 그리디로 풀었다가 풀리지 않아서 다시 풀었다.

그냥 마지막 광년은 무조건 1광년인줄 알아서 그전까지는 계속 증가되는 광념이 되도 상관 없는줄 알았다,

그래서 y-1 까지 증가되는 광년을 넘어오게 했지만 틀렸다...

 

답을 찾아보니 규칙을 찾아서 푼 사람들이 많았다.

 

1 : 1

2 : 2

3 : 3

4 : 3

5 : 4

6 : 4

7 : 5

8 : 5

9 : 5

10 : 6

11 : 6

12 : 6

13 : 7

14 : 7

 

이건 y-x의 크기와 최소로 넘어가는 수이다.

 

규칙을 찾다가 다른 사람들의 규칙을 찾다가 새로운 규칙을 찾았다.

내가 본 사람은 제곱수와 광년을 넘어가는 수의 방법의 대칭수를 찾아서 규칙을 줬는데

제곱수를 보고 깨달았다. 

sqrt(y-x) * 2 를 하면 정수형이 최소로 넘어가는 수이다.

이 규칙을 찾으면 쉽게 풀 수 있다.

 

근데 규칙을 찾았는데 틀려서 나처럼 푼 사람의 답을 보니 -1e-9를 해주었다.

 

#코드

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

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

    int t;
    cin >> t;
    long long x, y;
    while (t--) {
        cin >> x >> y;
        cout << floor(2 * sqrt(y-x)- 1e-9) << '\n';
    }
}