[BOJ-1011] Fly me to the Alpha Centauri

[문제]

이동 규칙

1. 다음에 이동할 수 있는 거리(광년)는 현재 이동거리의 현재 이동거리, +1 또는 -1이다.
   • 현재 3을 이동했다면 다음에 이동할 수 있는 거리는 2, 3, 4 중에 하나이다.
2. 마지막 이동거리는 1이여야 한다.

위의 이동 규칙을 가지고 현재 x지점에서 y지점으로 가기 위해선 최소 몇 번 움직여야 할까?

 

 

 

처음에는 단순하게 brute-force, BFS를 사용하면 되지 않을까라고 생각했다.

처음에 1을 움직이고 그다음에는 1, 2를 큐에 넣고 그 다음에도 또 1,1,2,3을 큐에 넣고 이런 식으로 전체 탐색을 하다가 현재 지점이 y이면서 이동거리가 1였을 때를 찾으면 되지 않을까라고 생각했다.

 

하지만… 메모리 초과가 발생했다.

 

당연하게도 처음에 이동할 때를 제외하고는 3번씩 (-1, 현재, +1) 경우의 수가 늘어나는데 y는 최대 2^31-1까지 가능하고 x는 최솟값이 0이다. 그러면 최대 이동거리는 2^31-1가 될 수 있다는 것이다. 대충 계산해도 어마무시하다는 것을 알 수 있다.

 

그래서 다시 한번 생각해보다가 하나의 규칙을 발견하게 됐다. 바로 이동 규칙 1번과 2번에 의해 최종 이동거리는 1, 2, 3, …, n, n-1, n-2, …, 3, 2, 1과 같은 형태가 되어야만 한다는 것이다.

 

따라서 절반의 거리를 최대한 적게 이동한 후에 나머지를 그와 똑같이 되돌아오면 된다.

 

 

 

 

 

[풀이]

그러면 절반의 거리를 어떻게 되대한 적게 이동할 수 있을까?

바로 계속 +1씩 움직이는 것이다. 1, 2, 3, 4, …, n 이렇게 최대한 n만큼 이동한 후에 나머지를 그대로 되돌아오면 된다.

 

 

 

그러면 어떻게 해야 거리 k에 대해 최소 횟수를 구할 수 있을까?

바로 (1~n 까지의 합) + (1~(n-1)까지의 합) 중에서 k와 제일 가까운 값을 구하면 된다.

 

위의 그림을 바탕으로 총 3가지의 결과 값이 나올 수 있다.

 

 

public class Main {
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int i = 0; i < T; i++) {
			String[] strings = br.readLine().split(" ");
			int x = Integer.parseInt(strings[0]);
			int y = Integer.parseInt(strings[1]);

			long distance = y - x;

			int j = (int)Math.sqrt(distance); // 1~n까지의 합은 n*(n+1)/2 이다.
							// 1~n까지의 2개의 합이 distance이므로 n(n+1) = distance이다.
							// 따라서 n을 구하기 위해서는 sqrt(distance)를 해주면 된다.
			long beforeTotal = (j * (j - 1) / 2); // n-1까지의 이동거리의 합을 구한다
			long sum = (j * (j + 1) / 2); //n까지의 이동거리의 합을 구한다
			long total = sum + beforeTotal; // 최종 이동거리는 최소 n까지의 이동거리 + 
		            				// n-1 까지의 이동거리이므로 총 이동거리의 합을 구한다

			for (; distance > total; j++) { //이렇게 하나씩 distance까지 
            						// 갈 수 있을만큼 이동한다.
				beforeTotal = total;
				total = sum + sum + j + 1;
				sum += j + 1;
			}

			long maxVal = total == distance ? total : beforeTotal; // total == distance 이면 
										// 1~n + n-1~1까지 합이 distance와 같기 때문에 더 이상 움직이지 않아도된다.
										// 하지만 total이 더 크다면 n까지 움직이면 안되고 n-1까지만 움직여야 하므로 
										// beforeTotal까지만 움직여야 한다.
			j = total == distance ? j : j - 1; //위와 마찬가지이다. total == distance 이면 j = n이고, 그렇지 않으면 n-1까지만 움직인다

			if (distance - maxVal == 0) { // (? = 0 인 경우)distance - maxVal == 0 이란 건 total과 distance가 같았다는 것이다. 
            							  // 따라서 1~n, (n-1)~1까지 움직였다는 것 이므로 최종 이동횟수는 n + (n-1)이다.
				System.out.println(j + j - 1);
			} else if (distance - maxVal > j) { 	// (? > n 인 경우)만약 distance - maxVal이 n보다 크다면 최대로 n+a 만큼 움직여야 된다는 소리다.				
				System.out.println(j + j - 1 + 2);  // a는 1~(n-1)까지가 될 수 있는데 n이 되는 순간 위의 for문에서 j는 n이 아닌 n+1이 될 것이기 때문에 
                						// a는 최대 n-1까지 밖에 될 수 없다.
			} else { // (? <= n 인 경우)그외에는 나머지 움직이는 값이 n보다 같거나 작다는 것인데 이것은 해당 값만큼 이동을 해주면 되는것이기 때문에 1만 더 해주면된다.
				System.out.println(j + j - 1 + 1);
			}
		}
	}
}