문제

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

---

입력

입력의 첫 줄에는 테스트케이스의 개수 T가 주어진다. 각각의 테스트 케이스에 대해 현재 위치 x 와 목표 위치 y 가 정수로 주어지며, x는 항상 y보다 작은 값을 갖는다. (0 ≤ x < y < 231)

---

출력

각 테스트 케이스에 대해 x지점으로부터 y지점까지 정확히 도달하는데 필요한 최소한의 공간이동 장치 작동 횟수를 출력한다.

---

풀이

제한조건

• x는 항상 y보다 작은 값을 갖는다. (0 ≤ x < y < 231)

접근방법

단순 계산
BFS처럼 경우를 확인하며 확인하는 방법이 떠오르거나,
최소한의 이동을 보며 DP인가 라는 생각이 들 수 있다.

하지만, 생각보다 단순한 규칙으로, 수식으로만 풀 수 있다.

문제의 조건에서 마지막에 도달하기 직전에는 1의 속도로 움직여야한다. 라는 조건이 있다.
1->2->3 ... 으로 이동하여도 마지막에 1의 속도로 움직이기 위해 3->2->1 순으로 감속해야한다.
그말인 즉, 초반 증가하는 추세의 역순이 반드시 후반 감속하는 단계에서 나타난다는 것이다.

거리를 기준으로 최소 몇 번을 이동해야 하는가를 생각해보자.

거리	이동수	패턴
1	1
2	2	(1 1)
3	3	(1 1 1)
4	3	(1 2 1)
5	4	(1 2 1 1)
6	4	(1 2 2 1)
7	5	(1 1 2 2 1)
8	5	(1 2 2 2 1)
9	5	(1 2 3 2 1)
10	6	(1 2 2 2 2 1)
11	6	(1 2 3 2 2 1)
12	6	(1 2 3 3 2 1)
13	7	(1 2 3 3 2 1 1)
14	7	(1 2 3 3 2 2 1)
15	7	(1 2 3 3 3 2 1)
16	7	(1 2 3 4 3 2 1)

거리를 기준으로 살펴보자.
제곱수의 다음에는 항상 이동 카운트가 증가한다.
또한 제곱근이 더해지는 시점에도 값이 증가한다..!
e.g) 6(4+2) 12(9+3)
따라서 수의 범위를 나누어 계산하면 된다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int N;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = stoi(in.readLine());

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; ++i) {
			String[] inputs = in.readLine().split(" ");
			int dist = stoi(inputs[1]) - stoi(inputs[0]);
			int sqrtValue = (int)Math.sqrt(dist);

			if (sqrtValue == Math.sqrt(dist))
				sb.append(2 * sqrtValue - 1).append("\n");
			else if (dist <= sqrtValue * sqrtValue + sqrtValue)
				sb.append(2 * sqrtValue).append("\n");
			else
				sb.append(2 * sqrtValue + 1).append("\n");
		}
		System.out.println(sb);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}