[No. 1011] C++ Fly me to the Alpha Centauri 문제 해설

＃ 정답 코드는 맨 아래에 있습니다.

 

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 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 < 2^31)

출력

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

 

 

---

백준알고리즘을 천천히 풀면서 공부중인데 해석본이라 그런지 다소 어렵게 나온 부분이 많다. 하지만 이 문제는 그냥.. 문제 자체가 이해가 잘 안돼서 계속 들여다 보았다.

 

하이라이트로 보기쉽게 해놓았지만 다시 요약하자면

첫 지점은 무조건 1만큼만 이동이 가능하고 점점 1을 더해가며 속도를 붙일수 있다. 하지만 속도가 1 -> 3  혹은 3 -> 1  이런식으로 2이상으로 늘이거나 줄일수 없고 y지점 -1의 지점에선 무조건 속도가 1이어야한다.

 

여기서 필요한 조건이 몇개 보이는데, 일단 출발지점에서 도착지점 사이의 거리를 구해야하고 또 일정한 규칙을 찾아야한다. ( 총 거리 = 도착지점 - 출발지점 )

 

그리고 위 규칙을 생각하며 하나하나 펜으로 그렸었는데, 요약하자면 총 거리가 4일때, 9일때, 16일때 최대 속도가 변화했다.

무슨 말이냐하면, 총 거리 = 도착지점 - 출발지점인데, 총 거리가 4일때, 이동을 1 - 2 - 1로 하게된다.

마지막과 첫지점은 1 고정이고, 중간을 최소한으로 이동해야하기에 2가 되고

 

총 거리가 9일때는 이동을 1 - 2 - 3 - 2 - 1인데, 첫지점과 마지막 지점은 1이고 한번에 +1씩 혹은 -1씩만 증가가 되고 최소 이동을 해야하기때문에 위와같이 나왔고

 

총 거리가 16일때는 이동을 1 - 2 - 3 - 4 - 3 - 2 - 1이다.

 

여기서 눈치채야 할 점은, 4는 2의 제곱, 9는 3의 제곱, 16은 4의 제곱이라는점이다.

 

즉 2N의 값부터 최대 속도가 갱신된다는 뜻이다.

 

추가로 입력란에 2^31 즉 2의 31승은 int와 long형의 최대값으로 백준 알고리즘 기준에서 입력하면 에러가 나기에 long long형으로 해주어야한다.

 

아직 부족하다, 조금 더 들여다 보았다. 

N의 값을 간편하게 구하려면 Y광년의 제곱근을 정수형으로 구하면 된다.

 

예로들어) 8이란값의 제곱근은 ‭2.82842712474619‬이다. 이를 정수형으로 바꾸어주면 2가 나오게된다.

이로써 N = 2이다.

 

여기서 최소 이동 횟수를 구해야하는데,

4 = 1 + 2 + 1 = 2 * 2  :: 최소 이동 횟수 -> 3

9 = 1 + 2 + 3 + 2 + 1 = 3 * 3 :: 최소 이동 횟수 -> 5

16 = 1 + 2 + 3 + 4 + 3 + 2 + 1 = 4 * 4 :: 최소 이동 횟수 -> 7

25 = 1 + 2 + 3 + 4 + 5 + 4 + 3 + 2 + 1 = 5 * 5 :: 최소 이동 횟수 = 9

 

위 예제를 보면 2N-1 == 최소 이동 횟수라는 공식이 성립된다.

 

여기서 우리는 저 숫자뿐만이 아닌 10, 15 , 8 등등의 숫자도 구해야하기에 우린 남은 거리또한 계산해주어야한다.

 

예로들어 8광년 떨어진 행성을 간다는 가정하에 계산을 해보자면

8광년 = N^2 + α이고

8의 제곱근은 2, 즉 N=2

 

이건 즉 2^2 + α이고 α = 4라는 결과가 나온다.

 

우선 나머지 거리를 구하는 공식을 알아내야하는데, 거리가 8인경우 5, 4인경우 3  즉 이동 횟수가 2가 차이가 나고

 

예로들어 거리가 13인경우 7, 9인경우 5  ( 13의 α값은 4 , 9의 α값은0)

또 22인경우 9, 16인경우 7이다. ( 22의 α값은 6 )

 

거리가 몇 차이건 최소 이동횟수는 2씩 차이가 나는데,

이는 즉 나머지거리 = (거리 - N^2) / N

위 계산공식이 나온다. 

 

요약해서 22의 최소 이동 횟수를 계산하자면

MD = 기본 최소 이동 횟수

N = 최대속력

RD = 나머지거리

A = 추가 거리

 

R = 결과

 

22 = N^2 + A

N^2 = √22 = 4

즉 22 = 4^2 + A = 16 + A

22 - 16 = A -> 6

 

N = 4

MD = (2N-1) -> (2*4-1) -> 7

RD = ?

A = 6

 

RD = (A/N) = 6/4 = 1...... (거리가 부족하면 도착을 못하니 올림으로 계산) -> 2

 

이로써 필요한 숫자는 다 구했다.

N = 4

MD = 7

RD = 2

A = 6

 

결과는 기본 최소 이동 횟수 + 나머지거리

즉 R = MD + RD -> R = 7 + 2;

 

즉 22의 최소 이동 횟수는 9가 나온다.

 

핵심을 다시한번 요약하자면

X광년을 구할때의 공식 -> N^2 + A

최소 이동 횟수 -> (2N-1)

최대 속력 -> N

나머지 거리 -> A/N

 

저 숫자들만 골라서 차례대로 계산해 조합하면 값이 나온다.

 

 

 

 

 

코드 주의

 

---

#define _CRT_SECURE_NO_WARNINGS 
#include <iostream>
#include <cmath>

int main()
{
	int nInputTestCase{};

	scanf("%d", &nInputTestCase);
	long long longDeparture{};
	long long longDestination{};
	long long longTotalDistance{};
	int nMaxSpeed{};
	int nMinimumMoveCount{};
	long long longRemainingDistance{};
	long long longResult{};
	for (int i = 0; i < nInputTestCase; i++)
	{
		scanf("%lld %lld", &longDeparture,&longDestination);

		longTotalDistance = longDestination - longDeparture;
		nMaxSpeed = sqrt(longTotalDistance);
		int nTempValue = pow(nMaxSpeed, 2);
		nMinimumMoveCount = 2 * nMaxSpeed - 1;
		longRemainingDistance = (long long)ceil(((double)longTotalDistance - (double)nTempValue) / (double)nMaxSpeed);

		longResult = nMinimumMoveCount + longRemainingDistance;

		printf("%lld\n", longResult);
	}
}

 

longDeparture = 출발지점

longDestination = 도착지점

longTotalDistance = 총 거리

nMaxSpeed = 최대 속도

nMinimumMoveCount = 최소 이동 횟수

longRemainingDistance = 나머지 거리

longResult = 결과값

 

c++기준 cmath를 추가시켜주었고 sqrt로 제곱근을 int형으로 구한 뒤 pow로 int형을 제곱해주었는데 없어도 딱히 상관 없을거 같긴한데, 이미 정답으로 처리된 상태라 그냥 두었다.