백준 1011_Fly to the Alpha Centauri [C++]

문제

 

 

풀이

 이 문제는 문제를 이해하는데에는 큰 시간이 걸리지 않았던 것 같은데, 풀이를 하는 과정에서 반복문을 사용할 경우 시간이 초과되는 문제가 발생해서 애를 먹었던 문제입니다.

 이 문제에서 처음 이동할 수 있는 거리는 -1,0,1 이나 실질적으로 -1과 0의 거리를 이동할 일이 없기 때문에 1만큼 이동하고, 그 다음은 0,1,2 의 거리를 이동할 수 있다는 뜻입니다. 그리고 도착 직전 마지막 이동거리는 1이 되어야 하므로, 마지막 이동 직전 거리는 1또는 2라는 것을 알 수 있습니다. 이런식으로 거리에 따른 이동 수를 나타내어 규칙을 알아보겠습니다.

총 이동거리(y-x)	이동거리	이동 수
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

 

이 표를 보면 n의 제곱일때를 기준으로 다음 수에서 이동수가 +1이 되며,  n의 제곱과 n+1의 제곱의 중간 값을 기준으로 이동 수가 +1이 되는 것을 알 수 있습니다. 즉 n을 총 거리의 제곱근으로 잡고, 거리가 n*n일 때와 n*n< 거리 <=(n+1)*(n+1)-(n+1) 일때,  (n+1)*(n+1)-(n+1)<거리<(n+1)*(n+1) 일 때를 기준으로 출력을 계산하여주면 문제를 해결할 수 있습니다.

소스코드는 아래와 같습니다.

 

 

소스코드

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


int main(){
    long long t, x, y, ly=0;
    cin >> t;
    for (int i =0 ; i < t; i++)
    {
        cin >> x >> y;
        ly=y-x;   
        long long n= (int)sqrt((double)ly);
        if (ly==n*n) cout<<1+2*(n-1)<<'\n';
        else if(n*n<ly && ly<=(n+1)*(n+1)-(n+1)) cout << 1+2*(n-1)+1 << '\n' ;
        else if((n+1)*(n+1)-(n+1)<ly && ly<(n+1)*(n+1)) cout << 1+2*n << '\n';
    }
}