[백준] 1011번 C++ "Fly me to the Alpha Centauri" 풀이 / 수학

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

1011번: Fly me to the Alpha Centauri

 

 

💡 Fly me to the Alpha Centauri

 

 

✅ 문제 풀이

• 시작지점 x와 끝지점 y의 사이 거리를 구하고, 그 거리는 최소 몇번의 이동이 필요한지 구한다.
• 무조건 처음시작과 마지막 이동은 1씩 이동한다. 따라서 y-x에서 2(처음, 끝)를 뺀 거리만을 가지고 몇번 이동할 수 있는지 구하면 된다.
• 만약 y-x-2의 결과가 0 이하라면, 즉 y-x가 1 또는 2 였다면, 시작과 끝을 제외하고는 중간에서 이동하는 거리가 없기 때문에 1이면 1번 이동하는것이고, 2이면 2번 이동하는 것이된다.
• 다음과 같은 수학적 규칙에 따라 거리마다의 최소 이동 횟수를 구할 수 있다.

• 시작과 끝의 각각 1만큼의 이동 거리를 빼고 생각해보자.
• dis = y-x-2 일때, dis가 1일때부터 이동 횟수를 구해보자. 이때 처음이 1이고, 마지막도 1이었기 때문에, 시작도 마지막도 (0,1,2)에서 고를 수 있게 되어야 한다.
• 1 : 1 => 1
  2 : 2 => 1
  3 : 1,2 => 2
  4 : 2,2 => 2
  5 : 1,2,2 => 3
  6 : 2,2,2 => 3
  7 : 2,3,2 => 3
  8 : 2,2,2,2 => 4
  9 : 2,3,2,2 => 4
  10 : 2,3,3,2 => 4
  11 : 2,3,3,2,1 => 5
  12 : 2,3,3,2,2 => 5
  13 : 2,3,3,3,2 => 5
  14: 2,3,4,3,2 => 5
  15 : 2,3,4,3,2,1 =>6
  16 : 2,3,4,3,2,2 => 6
  17 : 2,3,4,3,3,2 => 6
  18 : 2,3,4,4,3,2 => 6
  ...
  보면, 규칙이 있는걸 확인할 수 있다.
  이동횟수가 1인게 2개, 2인게 2개, 3인게 3개, 4인게 3개.... 
  두 묶음씩 동일한 이동횟수를 갖는 dis의 개수가 하나씩 늘어나고 있다.
  (이동 횟수) => dis의 개수 로 따지면
  (1,2) => 2+2
  (3,4) => 3+3
  ...
  dis의 개수가 같은 것끼리 묶어보면, 4, 6, 8, 10 ...이렇게 늘어나는 것을 알 수 있다.
  이를 누적하면 4, 10, 18, 28....인데, 이 수열을 수식으로 나타내보면 다음과 같다.
  a1 = 4
  a2 = a1+(a1+2)
  a3 = a1+(a1+2)+(a1+2+2)
  a4 = a1+(a1+2)+(a1+2+2)+(a1+2+2+2)
  ...
  an = n*a1+n(n-1) = n*n+3n 으로 정리할 수 있다.
• 이제 dis와 n^2+3n 을 가지고, n=1부터 계산하여 n^2+3n이 dis보다 작으면 n을 늘리고 dis보다 커지면 해당 n을 통해 이동 횟수를 구할 수 있다. 이는 while 문으로 n을 결정할 수 있다
•  이동횟수가 {1,2}인것부터 n=1이고, 그 뒤로 한 묶음씩 n을 늘려가면 된다.
• 예를 들어 dis가 15이면 n=3임을 구할 수 있는데, n*2를 한 6과 n*2-1를 한 5 둘 중 하나가 15의 최소 이동횟수 후보가 된다.
• 근데 n^2+3n-n인 n^2+2n보다 dis가 작으면 n*2-1에 해당하는 5가 답이 되는것이고, 그렇지 않으면 n*2에 해당하는 6이 답이 되는 것이다.

• 따라서 이러한 수학적 규칙과 식을 이용하여 이동 횟수를 쉽게 구할 수 있다.
• 이 문제에서 주의할 점은, 입력으로 주어지는 x와 y의 범위가 2^31까지 이기 때문에, int로 받아 계산하면 안되고, long long으로 받아 계산하여야 한다는 점이다.  

 

✏ 코드 전문

#include<iostream>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;

	for (int i = 0; i < t; i++) {
		long long s, e;//입력단위가 2^31이기 때문에 long long으로 받아야 data손실이 없음!!!
		cin >> s >> e;

		long long n = 1;
		long long dis = e - s - 2;

		if (dis <= 0) {
			cout << dis + 2 << "\n";
			continue;
		}

		while ((n*n + 3 * n) < dis) {
			n++;
		}

		if ((n*n + 2 * n) <= dis) n *= 2;
		else n = n * 2 - 1;

		cout << n + 2 << "\n";
	}

	return 0;
}