2022-06-13-fly-me-to-the-alpha-centauri-1011

• toc {:toc}

문제

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23 년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다.

그가 탑승하게 될 우주선은 Alpha Centauri 라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k 광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다. 예를 들어, 이 장치를 처음 작동시킬 경우 -1 , 0 , 1 광년을 이론상 이동할 수 있으나 사실상 음수 혹은 0 거리만큼의 이동은 의미가 없으므로 1 광년을 이동할 수 있으며, 그 다음에는 0 , 1 , 2 광년을 이동할 수 있는 것이다. ( 여기서 다시 2 광년을 이동한다면 다음 시기엔 1, 2, 3 광년을 이동할 수 있다. )

김우현은 공간이동 장치 작동시의 에너지 소모가 크다는 점을 잘 알고 있기 때문에 x 지점에서 y 지점을 향해 최소한의 작동 횟수로 이동하려 한다. 하지만 y 지점에 도착해서도 공간 이동장치의 안전성을 위하여 y 지점에 도착하기 바로 직전의 이동거리는 반드시 1 광년으로 하려 한다.

김우현을 위해 x 지점부터 정확히 y 지점으로 이동하는데 필요한 공간 이동 장치 작동 횟수의 최솟값을 구하는 프로그램을 작성하라.

입력

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

출력

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

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

풀이

1. 규칙성 먼저 생각. > 처음 시작할 때 1 광년만큼만 갈 수 있고 도착할 때도 1 광년만큼만 갈 수 있다. > 대칭성이 있다고 생각함.
2. 대칭적으로 움직일 때 몇 가지 경우를 생각해보니 case 를 분류할 수 있었음.
3. k 가 1 부터 시작해서 +1 씩 증가할 때 2(k+1) 보다 거리가 크면 횟수는 2 번씩 증가하고, k+1 < D < 2(k+1) 이면 2 번 증가하고 더 이상 이동하지 않아도 된다. D < k+1 이면 1 번 증가하고 더 이상 이동하지 않아도 된다.
4. 케이스 분류를 통해 문제 해결

#include <iostream>
 
using namespace std;
 
int main()
{
	int T, num, D, k, x, y;
	cin >> T;
	for(int i=0; i<T; i++)
	{
		cin >> x >> y;
		num = 0;
		k=1;
		D = y - x;
		if(D==1) num = D;
		else
		{
			num += 2;
			while(true)
			{
				if(D-2*k>2*(k+1))
				{
					D -= 2*k;
					num+=2;
					k++;
				}
				else if((k+1<D-2*k)&&(D-2*k<=2*(k+1)))
				{
					num+=2;
					break;
				}
				else
				{
					num+=1;
					break;
				}
			}
		}
		cout << num << endl;
		
	}
	
	return 0;
}