[C/C++] 백준 1011: Fly me to the Alpha Centauri(수열)

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

1011번: Fly me to the Alpha Centauri

온라인 코딩 문제 풀이 백준의 1011번 문제 Fly me to the Alpha Centauri 풀이

Fly me to the Alpha Centauri

문제 요약

• 이전에 공간 이동한 거리가 k라고 하면, 다음에 공간 이동할 수 있는 거리는 k-1, k, k+1이다.
• 처음 공간 이동 할 수 있는 거리는 1이다.
• 마지막 도착 지점에 도달하기 직전에 움직일 수 있는 거리는 1이다.
• 이 때 공간 이동의 최소한의 회수를 구하시오.

입력

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

출력

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

---

글이 빽빽하게 가득한 수학 문제만 보면 손발이 떨리고, 심장이 뛰는 사람에게는 이 문제는 위험해 보일 수 있다. 도대체 왜 우현이는 우주비행사가 되었고, 항성간 공간 이동을 왜 이렇게 어렵게 하는지. 하지만 실질적인 문제 부분만 잘 정리해서 확인해보면 조금 씩 풀어볼 만한 문제가 될 수 있다. 우선 이 문제는 수열에 관한 문제이다. 다음 공간 이동 거리는 이전 공간 이동 거리에서 1만큼 더하거나 같거나 1만큼 적어진다. 이런 수열 문제를 풀기 위해서는 초기값이 필요한데, 이 역시 1로 주어져 있다. 또한 최소한의 거리를 구하라고 했으니, 어떤 의미로는 최적화 문제라고 볼 수 있다. 마지막 공간 이동 거리는 1로 고정되어 있으므로 제한 사항(Constraints)이 포함도니 최적화 문제라고 생각 할 수 있다. 마지막으로는 테스트케이스에 대한 숫자는 $2^{31}$이다. 이는 제법 큰 값이라고 볼 수 있다. 즉, 프로그래밍을 할 때 각 변수에 대한 메모리 공간은 넉넉히 잡을 필요가 있다는 의미이다.

그렇다면 이 문제는 어떻게 풀 수 있을까? 먼저 이 문제의 구성은 수열을 통해 이동 거리/이동 회수에 대한 식을 세우고, 최소한으로 공간 이동한 경우를 찾아보면 된다. 수열에 대한 규칙을 찾기 위해 일단 직접 나열해 보자.

1	1
2	1, 1
3	1, 1, 1
4	1, 2, 1
5	1, 2, 1, 1
6	1, 2, 2, 1
7	1, 2, 2, 1, 1
8	1, 2, 2, 2, 1
9	1, 2, 3, 2, 1
10	1, 2, 3, 2, 1, 1

어떤 규칙이 보이는가? 혹시 안보인다면 더 많이 나열해 봐도 좋을 것 같다.

11	1, 2, 3, 2, 2, 1
12	1, 2, 3, 3, 2, 1
13	1, 2, 3, 3, 2, 1, 1
14	1, 2, 3, 3, 2, 2, 1
15	1, 2, 3, 3, 3, 2, 1
16	1, 2, 3, 4, 3, 2, 1
17	1, 2, 3, 4, 3, 2, 1, 1
18	1, 2, 3, 4, 3, 2, 2, 1
19	1, 2, 3, 4, 3, 3, 2, 1
20	1, 2, 3, 4, 4, 3, 2, 1

물론 여기서도 안보인다면 더 나열해 봐도 좋을 것 같다. 하지만 대략적인 규칙을 찾았으니 여기서 멈추는 게 분량을 위해선 좋을 것 같다. 최대한 일반화를 하자면, 대부분의 공간 이동 회수는 다음과 같이 쓸 수 있다.

$W_1(k) = \{1, 2, ..., k-1, k, k-1, ..., a+1, a, a, a-1, ..., 3, 2, 1| 0 \leq a < k, a \in \mathbb{Z} \}$

$W_2(k) = \{1, 2, ..., k-1, k, k, k-1, ..., a+1, a, a, a-1, ..., 3, 2, 1| 0 \leq a < k, a \in \mathbb{Z} \}$

공간 이동 수열 $W_1, W_2$는 모두 1부터 시작해 k까지 값이 1씩 증가하고, 이후 1씩 다시 감소하다가 a라는 값은 2번 반복된 다음 마저 작아져서 1이 된다. 둘 사이의 차이점은 k의 반복 여부이다.

다음은 여기서 k에 대한 값을 구하는 방법을 찾아야 한다. 각각의 수열들은 모두 더하면 총 이동 거리가 나와야 한다. 또한 각각의 수열들은 1부터 하나씩 증가하여 k가 되는 등차 수열이 반복되는 형태이기 때문에 다음과 같이 쓸 수 있다.(등차수열의 합)

${\sum}{W_1(k)} = \frac{k(k+1)}{2} + \frac{k(k+1)}{2} - k + a = k^2 + a$

${\sum}{W_2(k)} = \frac{k(k+1)}{2} + \frac{k(k+1)}{2} + a = k^2 + k + a$

두 식 모두 공통점은 1, ..., k까지의 등차수열의 합을 두번 계산한다는 점이다. 또한 모두 a가 반복 하여 나오므로 추가적으로 a를 더한다. $W_1$의 경우는 k를 빼는데, 이는 k가 중복하여 나오지 않기 때문이다.

또한 각각의 수열에 대한 이동거리는 다음과 같이 쓸 수 있다.

$N(W_1(k)) = 2k - 1 + \mathbb{1}(a > 0)$

$N(W_2(k)) = 2k + \mathbb{1}(a > 0)$

여기서 1(a > 0)는 a가 0보다 큰 경우에는 1, 아닌 경우에는 0을 갖는 함수이다. 이는 a가 0인 경우에 수열에 포함되지 않으므로 세지 않는다는 의미이다.

이 식을 통해 알 수 있는 것은 총 이동 거리가 $N$인 경우에 $W_1$이나 $W_2$의 총 합을 이용하여 최대 이동 거리 $k$를 계산 할 수 있다. 

예시 

총 이동거리 $N = 14$인 경우에 대해 먼저 계산해보자. $W_1$과 $W_2$중 우선 간단해 보이는 $W_1$을 활용해 보면, $k$의 값은 다음과 같다.

$k = \sqrt{14 - a}$

여기서 k는 정수여야 하므로, 이를 만족하는 가장 작은 $a$의 값은 5이다. 하지만 이렇게 되면 $k$는 3이 되므로 $a$가 $k$보다 커지게 되므로 집합 $W_1$은 불가능한 식이 된다. 그렇다면 $W_2$를 이용해 $k$의 값을 다시 구해보면 다음과 같다. (2차 방정식의 근해 공식)

$k = \frac{-1 + \sqrt{1 - 4a + 14\cdot 4}}{2} = \frac{-1 + \sqrt{57 - 4a}}{2}$

따라서 여기서도 제곱근 값이 정수가 되기 위해서 음이 아닌 정수 $a$의 최소값을 찾으면 2가 된다. 이 경우 $k$의 값은 3이 되고, $W_2(3) = {1, 2, 3, 3, 2, 2, 1}$이 되므로 수열의 총 합은 14가 된다.

이제부터 실질적인 코드를 보면 다음과 같다. 

#include <iostream>
#include <math.h>

using namespace std;

int64_t CalculateWarp(int64_t x, int64_t y)
{
	int64_t dist = y - x;
	int64_t res = 0;
	int64_t k, a;
	
	if (dist <= 3)
		return dist;

	k = (int64_t)sqrt(dist);
	a = dist - k * k;

	if (a >= k)
	{
    	// W_2
		int64_t sqrv = (int64_t)(sqrt(1 + 4 * dist));
		a = 1 + 4 * dist - sqrv * sqrv;
		k = (-1 + sqrv) / 2;
		if (a == 0)
		{
			// 1, 2, 3, ..., k-1, k, k, k-1, ..., a+1, a, a-1, 3, 2, 1
			res = 2 * k;
		}
		else
		{
			// 1, 2, 3, ..., k-1, k, k, k-1, ..., a+1, a, a, a-1, ..., 3, 2, 1
			res = 2 * k + 1;
		}

	}
	else
	{
    	// W_1
		if (a == 0)
		{
			// 1, 2, 3, ..., k-1, k, k-1, ..., a+1, a, a-1, 3, 2, 1
			res = 2 * k - 1;
		}
		else
		{
			// 1, 2, 3, ..., k-1, k, k-1, ..., a+1, a, a, a-1, ..., 3, 2, 1
			res = 2 * k;
		}
	}
	return res;
}

int main(void)
{
	int64_t T, x, y;
	cin >> T;

	for (int64_t t = 0; t < T; t++)
	{
		cin >> x >> y;
		cout << CalculateWarp(x, y) << "\n";
	}

	return 0;
}

먼저 main함수를 보면 T, x, y를 std::cin을 통해 받아 CalculateWarp함수의 결과를 출력하도록 되어 있다.

CalculateWarp는 x, y를 입력으로 받아 최소 공간 이동 회수를 계산하는 함수이다. x, y의 실질적인 좌표 값은 의미 없고, 상대적인 거리만 중요하기 때문에 dist = y - x를 계산한다.

여기서 dist가 3보다 작거나 같은 경우에는 이동 회수랑 같은 값을 갖고 있으므로 그대로 출력한다. 나머지는 위에 식을 통해 설명한 내용을 그대로 옮겨 적어 놓았다.

---

나름대로 풀이한 과정에 대해 상세히 적으려니 어려운 문제도 아닌데 쓸데없이 수열 이야기만 길게 한 것 같다. 실질적으로 필요한 수학 내용에 대해선 굵은 기울임 글씨로 표기해 놓은 것을 추가로 검색하면 좋을 것 같다.