백준 Gold 5 Fly me to the Alpha Centauri

Fly me to the Alpha Centauri (백준 Gold 5)

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

우주선을 조종하여
x 에서 y까지 이동하나

한번에 움직일 수 있는 거리는
이전 거리 k의

• k + 1
  
• k
  
• k - 1
  만 움직일 수 있다
  

또한 시작 속도는 1
마지막 도착 속도 또한 1일때

x->y 까지의 최소 이동횟수를 구하는 문제

풀이 방법

일반적으로 생각하는 그리디 or dp 문제는 아니였다
일단 주어지는 범위의 양이 상상을 초월하기에
해당 알고리즘들을 이용하는 경우
메모리 or 시간 초과 둘 중 하나가 발생해버린다

따라서 해당 문제는 수학적인 접근이 필요하다

일단 시작점과 끝점보다는
두 점사이의 거리가 문제의 핵심이며
힌트가 있다면
시작 속도와 끝 속도가 반드시 1이어야 한다는 점이다
‘또한’ 최소 이동횟수를 구하는 것이 문제이므로
전반적인 속도는 다음처럼 될 것이다

기본 구조
1 2 3 ... n ... 3 2 1
or

평탄 구조 (n이 k번 반복되어 완성)
1 2 3 ... n ... n ... 3 2 1

1부터 n까지 올라가게 되며
다시 n부터 1까지 떨어지게 된다

1부터 n까지의 합과 그 개수

• s(n) = (n^2 + n) / 2
  

따라서 1~n 이후 n-1 -> 1 은
s(n) + s(n-1)이 됨

• s(n-1) = (n^2 - n) / 2 로 요약 가능함
  

• (n^2 + n) / 2 + ((n-1)^2 + n - 1) / 2
  = n^2
  

또한 1~n 까지는 n개 있으며
n-1 까지는 n-1 개 있으니
2n - 1 개가 기본 구조의 개수가 된다
(그것이 ‘개수’니까)

그러면 평탄 구조에서는?

1 2 3 ... n,n ... 3 2 1

이런식으로 n을 1개 늘리게 되면

• 총 거리 합은 n^2 에서 n을 더하게 된
  n^2 + n
  
• 그리고 거리 개수는 2n 이 된다
  

만약 그런데도 ‘거리’가 부족하게 된다면
아예 단계를 올려야 한다
(n을 3개 사용하게 되는것보다 단계를 올리는것이
많은 거리를 커버 가능할 수 있음)

1 2 3 ... n, n+1, n ... 3 2 1

이렇게 되면

• 이전의 n^2 대신에 (n + 1)^2 부분 직전까지 체크할 수 있음
  
• 그리고 거리 개수는 2n + 1 이 된다
  

결론적으로?

결국 우리가 가야할 거리 distance가
위에서 말한 총 거리 합이다

따라서 먼저 거리 distance를
sqrt로 나눈 값을 n이라 하면

n * n 이 distance가 된다면

1 2 3 ... n ... 3 2 1

기본 구조가 되는 것이므로
그대로 2n - 1 을 return 하면 된다

그렇지 않다면
n을 하나 더한 거리인
n^2 + n 까지 검사해보고
그 범위안에 든다면 2n을,

그래도 안되면
2n+1을 return 해주면 끝

제출 코드

#include<iostream>
#include<math.h>

using namespace std;

long getN(long dis)
{
	long n = sqrt(dis);
	long ns = n * n;

	if (ns == dis)
		return n * 2 - 1;

	if (dis > ns && dis <= ns + n)
		return n * 2;

	return n * 2 + 1;
}

int main()
{
	int t;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		int x, y;
		cin >> x >> y;

		cout << getN(y-x) << '\n';
	}

	return 0;
}

결과

솔직히 조언 관련하여 검색하지 않았으면 풀지 못했을것 같다…
수학적인 부분에 대한 유연성이 있어야 풀 수 있을것 같은 문제였다