[백준 1011] Fly me to the Alpha Centauri 통찰노트

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
    https://github.com/AeroCodeX/

Fly me to the Alpha Centauri

문제를 대충 요약하면, 다음 조건을 갖는 최적화 문제와 같다.

워프거리는 위의 점화식을 만족해야 하고,
출발할때는 1로 출발해야 하며,
도착할때도 1로 도착해야 한다.
다만, 최소횟수로 워프해야 한다.

조건 (1, 2, 4)에 의해 속력은 출발점에서 우쪽으로 선형 증가하며,

조건 (1, 3, 4)에 의해 속력은 도착점에서 좌측으로 선형 증가하고,

조건 (1)에 의해 그래프는 연속이어야 한다.

즉, 위의 조건을 모두 만족하는 그래프는 다음과 같은 형태일 것 이다.

아래는 짝수 횟수로 최대 워프할 때의 그래프.

아래는 홀수 횟수로 최대 워프할 때의 그래프.

그래프의 넓이 구하기

그래프 안의 면적은 최대 워프거리임을 눈치챘다면 이제 문제가 한결 쉬워졌다.

n번으로 워프할 수 있는 최대 워프거리를 MaxWrap(n) 이라고 했을 때,

입력으로 주어지는 데이터는 수직선 상의 두 점(from, to)이므로, 둘 사이의 거리를 구한 후,

처음으로 to - from <= MaxWrap(n)을 만족하는 n을 반환하면 된다!

규칙 구하기

위의 그래프를 사용하되, 더 빠르게 동작하도록 개선할 수 있다.

이전 그래프와 다음 그래프는 꼭대기만 다르다는 것 이다.

다음은 각각 n, n+1, n+2 번째의 그래프 모양이다.

     

이해가 잘 되지 않는다면 아래 설명을 참고하라.

진짜 꼭대기만 다르다.

꼭대기만 적절히 더해주자.

대부분의 곱셈연산을 덧셈으로 대체하였으므로 이전보다 훨씬 빠르게 동작할 것 이다.