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

문제 바로가기

수학을 이용하는 문제다. 내 경험 상 이런 문제를 풀 땐, 차근차근 손으로 풀어가며 패턴을 찾아야 한다.

이 문제도 그렇게 풀기 시작했다. 그랬더니 역시나 패턴이 보였다.

$$1:1$$

$$2:1,1$$

$$3:1,1,1$$

$$4:1,2,1$$

$$...$$

$$9:1,2,3,2,1$$

$$10:1,1,2,3,2,1$$

좌우대칭이다. 아닌 것도 있지만... 일단 어느정도 좌우대칭의 성질을 가지고 있다.

또한, 가운데를 기점으로 양 옆으로 1씩 차이가 나는 등차수열을 어느정도 이룬다.

여기까지 생각한 나는 다음과 같은 식을 세웠다.

$$L=2\sum _{i=1}^{n}i+K$$

위에서 $L$은 $y-x$이다.

하지만 이렇게 했을 경우 $K$의 값을 어떻게 처리하냐에 따라 너무 많은 갈림길이 나온다.

그래서 차근차근 다시 생각해보기로 했다.

$$1:1$$

$$2:1,1$$

$$3:1,1,1$$

$$4:1,2,1$$

$$5:1,1,2,1$$

$$6:1,2,2,1$$

$$...$$

$$9:1,2,3,2,1$$

$$10:1,1,2,3,2,1$$

파란 색은 추가된 요소, 빨간 색은 값이 증가된 요소이다.

규칙을 나열해보면 아래와 같다.

$L$	$sequence$	$\text{number of elements}$	$operation$
$1$	$1$	$1$	$insert$
$2$	$1,1$	$2$	$insert$
$...$
$13$	$1,1,2,3,3,2,1$	$6$	$insert$
$14$	$1,2,2,3,3,2,1$	$6$	$increase$
$15$	$1,2,3,3,3,2,1$	$6$	$increase$
$16$	$1,2,3,4,3,2,1$	$7$	$increase$
$17$	$1,1,2,3,4,3,2,1$	$8$	$insert$
$18$	$1,2,2,3,4,3,2,1$	$8$	$increase$
$19$	$1,2,3,3,4,3,2,1$	$8$	$increase$
$20$	$1,2,3,4,4,3,2,1$	$8$	$increase$

$L$이 1부터 증가하면서 각 값에 따른 작업을 나열하면 아래와 같다.

$$insert/insert$$

$$insert,increase/insert,increase$$

$$insert,increase,increase/insert,increase,increase$$

$$insert,increase,increase,increase/insert,increase,increase,increase$$

보다시피 규칙성이 명확하다. $insert$가 될 때에는 요소의 수가 1 증가한다.

위를 참고하여 $L$의 길이에 따라 다음과 같이 묶을 수 있다.

$$(1/2),(3,4/5,6),(7,8,9/10,11,12),...$$

각 묶음이 끝나는 위치는 아래 식과 같다.

$$\sum _{i=1}^{n}2i$$

따라서, $L$이 주어졌을 때, 그 위치를 파악하고 그에 따른 요소 개수를 알아내는 식을 세울 수 있다.

우선 위치를 이용하는 방식은 이전에 풀었던 백준 1193번: 분수찾기에서와 유사하다.

$L$보다 큰 위 식의 결과 중에서 가장 작은 값과 $L$의 차이를 $n$과 비교하여 답이 나뉘는데,

$n$보다 작으면 $2n$, $n$보다 크면 $2n-1$이다.

위에 열거한 숫자들과 각 요소의 개수가 어떻게 되는지 생각해보면 유추할 수 있다.

식을 정리하면 다음과 같다.

$$answer=\{\begin{array}{ll}2n& \sum _{i=1}^{n}2i-L<n\\ 2n-1& \sum _{i=1}^{n}2i-L\ge n\end{array}$$

이를 코드로 나타내면 아래와 같다.

#define EL "\n"

#include <iostream>

using namespace std;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int T;
	cin >> T;
	
	int x, y, L;
	while (T--) {
		cin >> x >> y;
		L = y - x;
		
		int n = 1;
		unsigned int sum = 0;
		while (sum < L) {
			sum = n * (n + 1);
			n++;
		}
		n--;

		int diff = sum - L;
		if (diff < n)
			cout << 2 * n << EL;
		else
			cout << 2 * n - 1 << EL;
	}

	return 0;
}