#1011번 Fly me to the Alpha Centauri (c++)

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

int calculate(double a, double b){
    double ans = 0;
    double i=0;
    
    for(; ; i++){
        if(i*i>b-a)
            break;}
            
    i-=1;
    
    if(i*i==b-a) ans = i*2-1;
    else if(i*i<b-a&&b-a<=i*i+i) ans = i*2;
    else ans = i*2+1;
    
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T;
    int a[T];
    
    for(int i=0; i<T; i++){
        double start = 0; double end = 0;
        cin >> start >> end;
        if(end-start<=3) a[i] = end-start;
        else a[i] = calculate(start,end);}
        
    for(int i=0; i<T; i++)
        cout << a[i] << "\n";
    
    return 0;
}

푸는데 꽤나 애를 먹었던 문제. 

 

2월 쯤 하루 이틀에 걸쳐 문제 풀이 방법을 알아내려고 끙끙 앓았다가

오늘에서야(?) 심심해서 풀어보고 결국 해결한 문제였다. 

 

결국 다른 사람이 알아낸 핵심 포인트를 알아낸 후에야 혼자 코딩을 끄적여 볼 수 있었다. 

 

처음에 문제를 풀때, 이런 방식으로 생각해보았다. 

 

1. 도착지 - 출발지의 1/2까지 해당되는 지점까지 도달한다. 

2. 도달할 때 1/2지점을 초과하지 않도록, 변수를 잘 설정한다. (이 '잘'이라는 포인트 때문에 지저분한 코딩이 완성됐다.)

3. 구한 다음 총 이동횟수의 x2를 하면 정답 완성.

 

어지간한 테케는 다 통과했었으나, 채점과정에서 시간초과를 달성해버렸다. 

그러다가 이 문제의 핵심 포인트를 우연찮게 알게 됐는데, 그건 바로  

 

이동거리가 X의 제곱근(X>=1) 이상이면 이동 거리에 반드시 X가 포함된다는 점.

자세한 내용은 하단의 게시글을 참고해보자. 예시의 설명이 잘 되어있다. 

https://jm-park.github.io/algorithm/2018/08/01/백준-1011번-Fly-me-to-the-Alpha-Centauri.html 

JM's IT Blog

위의 법칙을 알아낸 다음은 일사천리로 해결되었다. 

 

열심히 노트에 끄적이며 내 스스로 다음 법칙을 알아냈는데, 이는 다음과 같다. 

 

1. X^2-X 초과 X^2 이하 까지는 2X-1의 이동 횟수 -> if에 해당됨

2. X^2초과 X^2+X 이하 까지는 2X -> else if에 해당됨

3. X^2+X초과 (X+1)^2이하 까지는 2X+1 -> else에 해당됨

 

타인에게서 알아낸 공식과 스스로 알아낸 공식을 합치니 문제는 푸는게 생각보다 쉬워졌다. 

 

혹시 테스트 케이스가 필요하다면 하단의 게시글을 참고하자.

 

https://www.acmicpc.net/board/view/26059

글 읽기 - ★★★ 필독!!! ★★★ Fly Me FAQ ★★★ 안 읽으면 후회! ★★★

 

풀기 위해선 약간의 노가다가 필요한 수학 문제 파트