[백준/C++] Fly me to the Alpha Centauri (No. 1011)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 잘 생각하면 쉽게 풀이방법을 생각할 수 있다.

 

이동거리가 1 증가, 그대로, 1 감소 3가지 경우 중 하나기 때문에 최대한 빠르게 이동하려면

1, 2, 3, 4, ... n-1, n, n, n-1, ... 3, 2, 1 와 같은 방법으로 이동하는 게 가장 빠르다.

 

이를 이용해 (1~n, n~1)의 이동거리가 y와 x 의 거리의 차이보다 작거나 같으면서 가장 큰 n을 찾으면 된다.

 

예를 들어 만약 y와 x의 거리 차이가 7이라고 가정해보자.

 

그러면 위 조건을 만족하는 n은 2가 된다.

 

이후 현재 이동거리가 1, 2, 2, 1로 6이며 y와 x의 거리차이는 7이므로 1만큼의 거리를 보충해주면 된다.

그러므로 1, 1, 2, 2, 1로 이동하면 5번의 최소 횟수로 조건을 만족하며 이동을 할 수 있다.

 

위 방법으로 풀 때 Case를 구분하면 아래와 같다.

 

y-x의 차이를 dist라고 하면

 

[1] 1~n, n~1의 합이 dist와 같은 경우

위 경우는 합이 dist와 같으므로 2*n번 이동해 가장 빠르게 도달할 수 있다.

 

[2] 1~n, n~1의 합이 dist보다 작은 경우

이 경우는 두가지 경우로 나눌 수 있다.

먼저 1~n, n~1의 합을 표현하면 n*(n+1)이다.

dist와 n*(n+1)의 차이가 n+1보다 작거나 같으면 2*n+1번 이동으로 도달할 수 있다.

 

왜냐하면 1~n의 거리차이가 나면 1~n의 경우를 한번 더 이동하면 된다.

n+1의 경우는 1~n, n+1, n~1로 n사이에 n+1을 한번 추가하면 된다.

 

나머지 경우는 2*n+2번 이동으로 도달할 수 있다.

 

남은 거리를 전부 2번 더 이동하는 것으로 완료할 수 있는 이유는 1~n, n~1의 합이 dist보다 작거나 같은 경우 중 가장 큰 n을 찾았기 때문이다.

dist-n*(n+1)의 값이 2*(n+1)보다 크거나 같은 경우는 위에서 찾은 n에서 벗어나므로 애초에 n+1값이 반환된다.

 

 

[아이디어 정리]

1. y와 x의 거리 차이가 n*(n+1) 보다 작거나 같은 경우 중 가장 큰 n을 찾는다.
2. dist-n*(n+1)의 값을 계산하고 경우에 따라 이동 횟수를 출력한다.

 

 

 

Code

 

 

 

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <queue>
using namespace std;

long long findN(long long dist)
{
    long long st = 0, ed = 100000,mid;
    long long N;
    long long ret;
    while (st <= ed) {
        mid = (st + ed) / 2;
        N = mid * (mid + 1);
        if (N > dist) {
            ed = mid-1;
        }
        else {
            st = mid + 1;
            ret = mid;
        }
    }
    // dist보다 작거나 같은 경우를 만드는 최대 N
    return ret;

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    for (int TC = 1; TC <= T; TC++)
    {
        long long x, y;
        cin >> x >> y;
        long long dist = y - x;
        findN(dist);
        long long N = findN(dist);
        long long cmpD = N * (N + 1);
        if (cmpD==dist)
        {
            cout << 2 * N << "\n";
        }
        else if (cmpD + N + 1 >= dist) {
            cout << 2 * N + 1 << "\n";
        }
        else {
            cout << 2 * N + 2 << "\n";
        }

    }

    return 0;
}

 

---

 

n을 찾으면 부족한 거리는 1~n 사이에서 그대로 이동하는 부분에 한번 추가하면 된다는 아이디어를 이용해 쉽게 풀 수 있는 문제였다.

 

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