[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 : {\color{blue}1}$$

$$2 : {\color{blue}1}, 1$$

$$3 : 1, {\color{blue}1}, 1$$

$$4 : 1, {\color{red}2}, 1$$

$$5 : 1, {\color{blue}1}, 2, 1$$

$$6 : 1, {\color{red}2}, 2, 1$$

$$ ... $$

$$9 : 1, 2, {\color{red}3}, 2, 1$$

$$10 : 1, {\color{blue}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{cases}2n & \sum_{i=1}^{n}{2i}-L<n\\2n-1 & \sum_{i=1}^{n}{2i}-L\geq n\end{cases}$$

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

#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;
}