백준 1011 - Fly me to the Alpha Centauri

문제 번호: 1011

문제 제목: Fly me to the Alpha Centauri

문제 주소: https://www.acmicpc.net/problem/1011

문제 내용

아래의 규칙을 통해 x에서 y로 이동하는데 필요한 최소한의 이동 횟수를 출력한다.
1. 최초 기준값 k는 0이다.
2. 이동 시에는 k - 1, k, k + 1 중 하나의 거리만큼 이동할 수 있다.
3. 다음 이동 시의 기준값을 직전에 이동한 거리가 된다.
4. 도착 시의 이동 거리는 1 이어야 한다.
5. 정지 또는 후진이 불가능하다.

테스트 케이

6 0 1 1 3 3 6 6 10 10 15 0 2147483647

1 2 3 3 4 92681

문제 풀이

이동 속도의 변화량은 1로 제한되어 있는데 도착 직전의 이동 거리가 1이어야 한다.
따라서 속도를 가속하다 중간 지점부터 감속을 해야 한다.
이를 그래프로 나타내면 아래와 같다.

위와 같이 이동 횟수별 이동 거리는 좌우대칭 형태를 이루고 있다.
현재의 (1회당 이동거리) * 2를 거리에서 빼는 작업을 거리가 0보다 작거나 같아질 때까지 반복하고
1. 거리 = 거리 - (1회당 이동 거리) * 2
2. 이동 횟수 +2
3. 거리가 0보다 작거나 같은가?
4. 아닐 경우 1회당 이동거리 +1
위 과정의 반복 완료 후에 (거리 + 1회당 이동거리) <= 0이 true일 경우 이동 횟수 -1을 하면 된다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_1011()
{
	int T;
	cin >> T;

	for (int i = 0; i < T; i++)
	{
		int x;
		int y;
		cin >> x >> y;	
		y -= x;

		int moveLength = 0;
		int moveCount = 0;
		while(y > 0)
		{
			moveLength++;
			y -= moveLength * 2;
			moveCount += 2;
		}
		if (y + moveLength <= 0)
		{
			moveCount--;
		}
		cout << moveCount << endl;
	}
	return;
}