[백준 알고리즘] 1011번 : Fly me to the Alpha Centauri

문제

1011번 : Fly me to the Alpha Centauri

1011번: Fly me to the Alpha Centauri

내가 작성한 코드 (C++ 성공)

#include <iostream>
#include <cmath>

using namespace std;

int main(){
	cin.tie(0);
	int t;
	cin >> t;
	
	long long x, y;
	
	for(int i=0; i<t; i++){
		cin >> x >> y;
		double dist = y-x; // 두 지점 사이의 거리
		double dpow = sqrt(dist); // 거리의 제곱근
		int pow = round(sqrt(dist)); // 거리의 제곱근을 반올림
		
		if(dpow <= pow) cout << pow * 2 - 1 << "\n"; 
		else cout << pow * 2 << "\n"; 
	}
		
	return 0;
}

 

정리

문제를 이해하려고 정말 많은 시간을 썼던 문제였다. 나만 이해가 안되는 걸까...?
처음에 이 문제를 보고나서 1 광년을 이동하면 다음에는 0, 1, 2 광년 위치로 이동하는 거 아닌가?
하고 문제를 풀었는데 당연히 틀렸다.
그래서 정말 문제가 이해가 되지 않아 여러 블로그를 보면서 이해했다.
그리고 다시 보고 나서 1 광년 이동하면 0 1 2 광년 만큼 이동할 수 있다고 문제를 제대로 이해할 수 있었다.
마지막 도착하기 전에 무조건 1광년만 이동할 수 있기 때문에
이동할 수 있는 거리를 줄여나가야한다는 사실을 뒤늦게 알았다.
따라서, 이 문제를 이해해보면

0광년 일 경우, 1광년 "만큼" 이동 가능 1광년을 이동했을 경우, 0 광년 또는 1 광년 또는 2 광년 "만큼" 이동 가능 2광년을 이동했을 경우, 1 광년 또는 2 광년 또는 3 광년 "만큼" 이동 가능 ... ... 10광년을 이동했을 경우, 9 광년 또는 10 광년 또는 11 광년 "만큼" 이동 가능

이런 식으로 이동할 수 있다.
처음에 이 문제를 보고 잘못 이해할 수 있는 부분이 해당 위치로 가는 것인지, 이동하는 것인지 헷갈릴 수가 있다.
따라서, 이런 방법을 통해서 x 지점부터 y 지점까지 이동하는데 필요한 최소한의 작동 회수를 구해야한다.

그러면 거리에 따른 이동할 수 있는 최소한의 횟수를 구해봐야한다. 표로 정리해봤다.

거리에 따른 최소 작동 횟수

이 표를 잘 보게되면 규칙을 찾을 수 있다.
각 거리의 제곱근(A)과 제곱근의 반올림한 값(B)을 비교한다.

A <= B 일 경우, ( 2 X B ) - 1 로 값을 구할 수 있고,
A  >  B 일 경우, 2 X B 로 값을 구할 수 있었다.