[BOJ] 백준 1011 Fly me to the Alpha Centauri

출처:  https://www.acmicpc.net/problem/1011

 Input 

3

0 3

1 5

45 50

 

 Output 

3

3

4

이동 거리: 로켓의 직전 이동 거리를 k라고 했을 때, 

                다음에는  『k-1』, 『k』, 『k+1』 거리만큼 이동

ex) 로켓 위치= 2 / 직전 이동 거리 k = 4일 때, 『3』 『4』 『5』 만큼 이동하여 

        다음 로켓 위치 = 5 or 6 or 7

* 출발점 x에서 k=1만큼 이동하여 로켓의 위치 = 1 

* 도착점 y에 도착하기 직전 이동거리는 반도시 『1』이어야만 합니다.

 

※ 최소 이동횟수에 따른 최대 이동거리 

[횟수]    [k]                                            

    1        1  ▶ 1

    2        1→1 ▶ 2

    3        1→2→1 ▶ 4

    4        1→2→2→1 ▶ 6

    5        1→2→3→2→1 ▶ 9 

    6        1→2→3→3→2→1 ▶ 12

    7        1→2→3→4→3→2→1 ▶ 16

    8        1→2→3→4→4→3→2→1 ▶ 20

    9        1→2→3→4→5→4→3→2→1 ▶ 25

 

문제 조건 중 도착점 y에 도착하기 직전 이동거리는 『1』이어야 하므로

로켓은 처음에는 가속하다가 중간지점부터 감속해야 최대한 이동할 수 있다.

(x, y 각각의 지점에서 숫자가 증가하는 형태)

ex) 총 이동해야 될 거리 = 15 (= y - x)일 때,

▶ 12 < 15 < 16 이므로 최소 7번의 이동횟수 필요.

ex) 총 이동해야 될 거리 = 17 일 때

▶ 16 < 17 < 20 이므로 최소 8번의 이동횟수 필요.

 

[참고]

 

Sample Case

 Input 

4

0 1

0 2

0 17

0 2147483647

 

 Output 

1
2
8
92681

---

import java.util.Scanner;
 
public class Main {
    public static void solutionFunc(long x, long y){
        // 출발지점과 도착지점을 이용하여 총 이동거리를 구한다.
        long distance = y - x;
         
        // 총 이동거리의 루트값의 버림값(올림값)을 기준점을 잡는다.
        long rDistance = (long) Math.sqrt(distance);
        long cri = (long) Math.floor(rDistance);
         
        long result;
        if(distance == Math.pow(cri, 2)){
            result = 2 * cri - 1;
        }else if(distance <= Math.pow(cri, 2) + cri){ 
            result = 2 * cri;
        }else{
            result = 2 * cri + 1;
        }
        System.out.println(result);
    }
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        // 테스트케이스 몇 개 인지 입력 받는다.
        long T = sc.nextLong();
         
        // 각 테스트케이스마다 출발지점과 도착지점을 담을 변수생성
        long[] x = new long[(int)T];
        long[] y = new long[(int)T];
         
        // 출발지점과 도착지점을 입력 받는다.
        for(int i=0; i<T; i++){
            x[i] = sc.nextLong();
            y[i] = sc.nextLong();
        }
        //System.out.println(Arrays.toString(x));
        //System.out.println(Arrays.toString(y));
         
        // 각 케이스마다 최소 이동횟수를 구해서 출력한다.
        for(int i=0; i<T; i++){
            solutionFunc(x[i], y[i]);
        }
    }
}