[백준 BOJ] 1011 Fly me to the Alpha Centauri

링크

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

1011번: Fly me to the Alpha Centauri

풀이

거리가 주어지고

1) 이전 작동시기에 k광년을 이동했을 때, k-1, k 혹은 k+1 광년만을 다시 이동할 수 있다.

2) 출발과 도착할 때의 속도는 1광년.

이라는 조건이 붙습니다.

 

공간 이동 장치 작동 횟수의 최솟값을 구하는 것이 목표입니다.

 

일단 이동 장치를 n번 썼을 때 갈 수 있는 최대 거리를 나열해 보겠습니다.

1              1       1*1
11            2       1*1 + 1
121          4        2*2
1221         6       2*2 + 2
12321       9       3*3
123321     12      3*3 + 3
1234321    16     4*4
12344321   20    4*4 + 4
123454321  25    5*5

 

거리의 합을 보면 이러한 규칙을 따른다는 것을 알 수 있습니다.

그러면 x y의 거리의 차와 i*i, i*i+i의 값을 비교해서 작거나 같을 때 출력해주면 문제를 해결할 수 있습니다.

출력 값은 i*i보다 작을 때 i*2-1 (홀수), i*2 (짝수)로 출력하면 됩니다.

 

거리의 차는 2^31보다 작지만 i*i 제곱 연산이 들어가고 이는 int의 범위를 벗어날 수 있기 때문에 long long int를 사용해줍니다.

 

 

코드

//1011_Fly me to the Alpha Centauri
#include <cstdio>
using namespace std;

int T, x, y;

int main() {
	scanf("%d", &T);

	while (T--) {
		scanf("%d %d", &x, &y);

		long long int d = y - x;
		long long int i = 1;

		while (true) {
			if (d <= i * i) {
				printf("%lld\n", i*2-1);
				break;
			}
			else if (d <= i * i + i) {
				printf("%lld\n", i*2);
				break;
			}
			i++;
		}
	}

	return 0;
}