[1011번] Fly me to the Alpha Centauri

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

위의 표를 보고 한번 생각해보자.

우리는 처음 입력을 통해 시작점과 끝점 사이 거리를 알 수 있게 된다.

그것을 dist라 해보자.

그렇다면 start, end를 입력 받으면 dist = end - start가 될 것이다.

이제 이 dist가 저 표와 어떻게 연관있는지 보자.

dist가 10이었다면 위의 표에 의해 n = 3일때 즉, 최대 9까지 간 후 1만 더가면 된다.

dist가 22였다면 n = 4일때 즉, 최대 16까지 간 후, 나머지 22 - 16인 6만 더 가면 된다.

위의 두 예를 들고 일반화 시켜보자.

n을 구하기는 쉽다. jump * jump > dist가 되는 부분에서 jump를 찾아주면 된다.

그리고 나머지 거리는 left = dist - (jump * jump);를 해주자.

그렇다면 나머지 거리가 남았는데 이것은 어떻게 처리할까?

즉 dist = 22, n = 4, 나머지 6일때 크기 4인 워프 내에서 적절히 조절해주면 된다.

1 2 3 4 4 3 2 2 1

즉, 이러한 값은 left / jump를 한 후 올림을 해주면 알 수 있다.( 6 / 4 = 1.5 -> 올림을 하면 2)

이 과정에 대한 원문은 다음과 같다.

https://www.acmicpc.net/board/view/13747

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include <iostream> #include <cstdio> #include <cmath>   using namespace std;   typedef long long ll;   int main() {     int tc;     scanf("%d", &tc);       while (tc--)     {         int start, end;         scanf("%d %d", &start, &end);           ll dist = end - start;           ll jump = 1;         for (;; jump++)             if (jump*jump > dist)                 break;         jump--;           ll left = dist - (jump * jump);         left = (ll)ceil((double)left / (double)jump);           printf("%lld\n", jump * 2 - 1 + left);     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus