BOJ [1011] Fly me to the Alpha Centauri

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

시작점 x부터 도착점 y까지 이동하는 문제. 이동 횟수를 구해야 한다.

이동 속도는 1부터 시작하고, 한 번 이동할 때마다 ±1씩 증감한다.

마지막 지점에 들어오는 속도는 반드시 1이 되어야 한다는 조건이 있다.

즉, 속도는 1씩 증가하여 중간 지점에서 최대치에 도달한 후 서서히 감소하여 다시 1로 돌아온다.

규칙을 찾아보기 위해 표로 정리해 보았다.

두 지점 사이의 거리	최적의 속도 변화
1	1
2	11
3	111
4	121
5	1211
6	1221
7	11221
8	12221
9	12321
10	112321
11	122321
12	123321
...	...

1번 이동 : 1항부터
2번 이동 : 2항부터
3번 이동 : 3항부터
4번 이동 : 4항부터
5번 이동 : 7항부터
. . .

위 결과를 항으로 정리한다.

A₁ = 1
A₂ = 2    (1항에서 1 증가)
A₃ = 3    (2항에서 1 증가)   
A₄ = 5    (3항에서 2 증가)
A₅ = 7    (4항에서 2 증가)
A₆ = 10  (5항에서 3 증가)
...
A_n+1 = A_n  +  | n/2 |

규칙만 알아낸다면 코드 작성은 간단하다.

#include <cstdio>

int main()
{
	int T;

	scanf("%d", &T);
	while (T--)
	{
		int x, y, ans = 1;
		unsigned int gap, pos = 1;
		scanf("%d %d", &x, &y);
		gap = y - x; // 두 지점 사이의 거리
		for (int i = 2; pos < gap; i++)
		{
			pos += i / 2; // pos는 현재 위치이며 gap보다 작아야 한다.
			ans++;
		}
		if (pos > gap)
			ans--;
		printf("%d\n", ans);
	}
	return 0;
}