[백준] 1011번 : Fly me to the Alpha Centauri [Java]

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

1011번: Fly me to the Alpha Centauri

 

---

 

 

● 문제

[백준] 1011번

 

 

 

 

● 접근 방법

k(n) = k(n-1) - 1 or k(n-1) or k(n-1) + 1 이다.

한마디로 다음 거리는 이전 거리보다 ±1 또는 같다.

 

현재위치 x와 목표위치 y와의 거리는 y - x이다.

 

첫 이동과 마지막 이동은 무조건 1이다.

 

[ 표1 ]

다음 표와 같이 y-x의 거리에서 나올 수 있는 최대 이동 거리는 거리의 제곱근 [내림] 이다.

이 규칙을 찾을 때, 많은 시간을 들였다.

이때 표를 확인해보면 제급수를 지날 때, count가 1 증가하는 것을 확인 할 수 있다.

 

그렇다면 max ^ 2을 생각해보자.

distance가 3일때, 3의 제곱근은 1.7xxx, 올림하면 2이다.

이 2(max)의 제곱은 4라는 것을 알 수있다. 그 값에 -1을 하면 count가 나오는 것을 확인할 수 있다.

 

▶ 하지만 굳이 max값을 올림을 해야할까?

여기서 나는 distance의 제곱근을 올리지 않고 계산한 후, 올림을 하였다.

 

distance가 3 일때 max 값은 1.73xxx 이다. 이곳에 1을 뺀 0.73xxx을 더하면 2.46xxx이다.

이것을 Math.ceil을 이용하여 올려주고, 형변환을 시켜주면, 이게 또 잘먹힌다. 

 

결론 : max값을 올림 후 계산하든 max값을 올리지 않고 계산하든 식만 다를뿐 원리는 비슷하다.

 

 

 

 

● 문제 풀이

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		long x, y;
		long a = 0;
		
		//입력
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		
		// 테스트 케이스
		for(int i = 0; i < t; i++) {
        	//입력
			x = sc.nextInt();
			y = sc.nextInt();
			
			//풀이
			double length = Math.sqrt(y - x);
			int answer = (int)Math.ceil(length + (length - 1));
			
			//출력
			System.out.println(answer);
		}
	}
}