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

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

1011번: Fly me to the Alpha Centauri

---

행성 X에서 행성 Y로 이동하는데 조건은 아래와 같다. 

• 이전에 k 광년을 이동했을 시 그다음 움직일  수 있는 거리는 k-1, k, k+1 이다.
• 처음과 마지막은 1광년만을 움직일 수 있다.

k=1, 1,2를 이동 가능 

k=2, 1,2,3을 이동 가능 

거리별로 움직일 수 있는 방법을 그림으로 간단히 일부만 그려봤다. 

이 그림을 가지고 규칙이 있는지 찾아볼 것이다. 

 

1의 거리를 이동해야 할 때 갈 수 있는 방법은 1이다.

2의 거리를 이동해야 할때 갈 수 있는 방법은 11이다.

3의 거리를 이동해야 할때 갈 수 있는 방법은 111 과 12이지만 12는 2로 끝나므로 111만 해당된다. 

4의 거리를 이동해야 할 때 갈 수 있는 방법은 1111과 121, 112이지만 122는 2로 끝나므로 1111,121만 해당된다. 이중 최소 움직임은 121이다. 

5의 거리를 이동해야 할 때 갈 수 있는 방법은11111,1121,1112,1211,122이지만 2로 끝나는 것을 제외하면11111,1121,1211이고, 이중 최소 움직임은 1121,1211이다.

 

이것을 표로 정리하면 이렇다.

답이 여러 개인 경우에는 이전 방법에서 뒤에 1을 붙이는 방법을 선택했다. 

여기서 규칙을 찾아보면

• 거리가 제곱의 수 일 때 121 혹은 12321 이런 식으로 진행이 된다.
• 각 최대 이동거리는 √거리이다(소수점 버린). 
• 이동 횟수는 최대이동거리를 max라고 했을 때, max*2-1이거나 max*2이거나 max*2+1이다. 

 

여기서 우리는 최소 이동 횟수를 구하는 것이 목적이므로 어느 때에 max*2-1이거나 max*2이거나 max*2+1가 되는지 알아내면 된다. 

max*2-1는 √거리= max 인경우 

max*2는 거리 <= max * max + max

max*2+1 그 외이다. 

 

---

import java.util.*;

public class Main {
	static int T;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();	//테스트 케이스 
		
		for(int i=0;i<T;i++) {
			int X=sc.nextInt();	
			int Y=sc.nextInt();	
			
			int dist = Y-X;	//행성간 거리
			int cnt=0;		//이동 횟수
			
			int max = (int)Math.sqrt(dist);	//최대 이동 거리 
			
			if(max == Math.sqrt(dist)) {
				System.out.println(max * 2 - 1);
			}
			else if(dist <= max * max + max) {
				System.out.println(max * 2);
			}
			else {
				System.out.println(max * 2 + 1);
			}
		}
	}// main()
	
}// class Main